fork download
copy 
  1. void solve(std::istream& in, std::ostream& out) {
  2. 		int n;
  3. 		in >> n;
  4. 		using Z = ZnConst<1000000007>;
  5. 		int mx = 2500001;
  6. 		vector<int> v(n);
  7. 		struct Info {
  8. 			int pos, ans;
  9. 			Z c;
  10. 		};
  11. 		vector<vector<Info>> infos(mx);
  12. 		//for (int i: range(mx)) { //initialize lazily
  13. 		//	infos[i].push_back({-1, 0, Z::rawValueOf(1)});
  14. 		//}
  15. 		struct PrefInfo {
  16. 			Z sum, sumcpos;
  17. 		};
  18. 		vector<vector<PrefInfo>> prefs(mx);
  19. 		//for (int i: range(mx)) {
  20. 		//	prefs[i].push_back({Z(), Z()});
  21. 		//	prefs[i].push_back({Z::rawValueOf(1), Z::valueOf(-1)});
  22. 		//}
  23.  
  24. 		vector<pair<int, int>> gcds;
  25. 		for (int i: range(n)) {
  26. 			in >> v[i];
  27. 		}
  28.  
  29. 		gcds.push_back({-1, -1});
  30.  
  31. 		for (int i: range(n)) {
  32. 			vector<pair<int, int>> newgcd;
  33. 			newgcd.push_back({-1, -1});
  34. 			for (auto j = 1; j < gcds.size(); ++j) {
  35. 				auto g = gcds[j];
  36. 				g.first = gcd(g.first, v[i]);
  37. 				if (g.first == newgcd.back().first) {
  38. 					newgcd.back().second = g.second;
  39. 				} else {
  40. 					newgcd.emplace_back(g.first, g.second);
  41. 				}
  42. 			}
  43. 			newgcd.emplace_back(v[i], i);
  44.  
  45. 			gcds = move(newgcd);
  46.  
  47. 			for (int j = 1; j < gcds.size(); ++j) {
  48. 				int g = gcds[j].first;
  49. 				if (infos[g].empty()) { // fixing mempry problems
  50. 					infos[g].push_back({-1, 0, Z::rawValueOf(1)});
  51. 					prefs[g].push_back({Z(), Z()});
  52. 					prefs[g].push_back({Z::rawValueOf(1), Z::valueOf(-1)});
  53. 				}
  54. 				auto endofgood = std::partition_point(infos[g].begin(), infos[g].end(), [&](Info info) {
  55. 					return info.pos < gcds[j].second;
  56. 				}) - infos[g].begin();
  57.  
  58. 				Info new_info = {i, -1, Z::valueOf(0)};
  59. 				new_info.ans = infos[g][endofgood - 1].ans + 1;
  60. 				auto start_of_same_answer = std::partition_point(infos[g].begin(), infos[g].end(), [&](Info info) {
  61. 					return info.ans < new_info.ans - 1;
  62. 				}) - infos[g].begin();
  63. 				auto center = std::partition_point(infos[g].begin(), infos[g].end(), [&](Info info) {
  64. 					return info.pos < gcds[j - 1].second;
  65. 				}) - infos[g].begin();
  66.  
  67. 				if (center >= start_of_same_answer) {
  68. 					new_info.c += (prefs[g][center].sum - prefs[g][start_of_same_answer].sum) * (gcds[j].second - gcds[j - 1].second);
  69. 				}
  70. 				int st = (int) max(center, start_of_same_answer);
  71. 				new_info.c += gcds[j].second * (prefs[g][endofgood].sum - prefs[g][st].sum) -(prefs[g][endofgood].sumcpos - prefs[g][st].sumcpos);
  72. 				infos[g].push_back(new_info);
  73. 				prefs[g].push_back({prefs[g].back().sum + new_info.c, prefs[g].back().sumcpos + new_info.c * new_info.pos});
  74. 			}
  75. 		}
  76.  
  77. 		int maxans = 0;
  78. 		for (int i: range(mx)) {
  79. 			if (!infos[i].empty()) {
  80. 				maxans = max(maxans, infos[i].back().ans);
  81. 			}
  82. 		}
  83.  
  84. 		Z res;
  85. 		for (int i: range(mx)) {
  86. 			for (auto t: infos[i]) {
  87. 				if (t.ans == maxans) {
  88. 					res += t.c;
  89. 				}
  90. 			}
  91. 		}
  92.  
  93. 		out << maxans << ' ' << res << "\n";
  94. 	}
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:17: error: variable or field 'solve' declared void
 void solve(std::istream& in, std::ostream& out) {
                 ^
prog.cpp:1:12: error: 'istream' is not a member of 'std'
 void solve(std::istream& in, std::ostream& out) {
            ^
prog.cpp:1:26: error: 'in' was not declared in this scope
 void solve(std::istream& in, std::ostream& out) {
                          ^
prog.cpp:1:30: error: 'ostream' is not a member of 'std'
 void solve(std::istream& in, std::ostream& out) {
                              ^
prog.cpp:1:44: error: 'out' was not declared in this scope
 void solve(std::istream& in, std::ostream& out) {
                                            ^
stdout
copy 
Standard output is empty
https://ideone.com/GSDPEg
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!