fork(4) download
copy 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <chrono>
  5. #include <climits>
  6. #include <cstdint>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <ctime>
  11. #include <deque>
  12. #include <fstream>
  13. #include <functional>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <map>
  17. #include <numeric>
  18. #include <queue>
  19. #include <random>
  20. #include <set>
  21. #include <stack>
  22. #include <sstream>
  23. #include <tuple>
  24. #include <vector>
  25.  
  26. using namespace std;
  27. using namespace chrono;
  28.  
  29. #ifdef DEBUG
  30. 	//#define LOCAL_INPUT_FILE
  31. #else
  32. 	//#define USE_FILE_IO
  33. #endif
  34.  
  35. #ifdef USE_FILE_IO
  36. 	#define INPUT_FILE "input.txt"
  37. 	#define OUTPUT_FILE "output.txt"
  38. 	#define cin ____cin
  39. 	#define cout ____cout
  40. 	ifstream cin(INPUT_FILE);
  41. 	ofstream cout(OUTPUT_FILE);
  42. #else
  43. 	#ifdef LOCAL_INPUT_FILE
  44. 		#define cin ____cin
  45. 		ifstream cin("input.txt");
  46. 	#endif
  47. #endif
  48.  
  49. const int infinity = (int)1e9 + 42;
  50. const int64_t llInfinity = (int64_t)1e18 + 256;
  51. const int module = (int)1e9 + 7; 
  52. const long double eps = 1e-8;
  53.  
  54. mt19937_64 randGen(system_clock().now().time_since_epoch().count());
  55.  
  56. inline void raiseError(string errorCode) {
  57. 	cerr << "Error : " << errorCode << endl;
  58. 	exit(42);
  59. }
  60.  
  61. int block = 200;
  62.  
  63. struct Query {
  64. 	int l, r, idx;
  65.  
  66. 	inline pair<int, int> toPair() const {
  67. 		return make_pair(l / block, ((l / block) & 1) ? -r : +r);
  68. 	}
  69. };
  70.  
  71. inline bool operator<(const Query &a, const Query &b) {
  72. 	return a.toPair() < b.toPair();
  73. }
  74.  
  75. signed main() {
  76. 	#ifndef USE_FILE_IO
  77. 		ios_base::sync_with_stdio(false);
  78. 	#endif
  79.  
  80. 	mt19937 rnd(42);
  81.  
  82. 	int n, m, k; cin >> n >> m; k = rnd() % 1048576;
  83. 	vector<int> p(n+1);
  84. 	for (int i = 0; i < n; i++) {
  85. 		int val = rnd() % 1048576;
  86. 		p[i+1] = p[i] ^ val;
  87. 	}
  88. 	block = sqrt(n) + 1;
  89.  
  90. 	vector<Query> qry(m);
  91. 	for (int i = 0; i < m; i++) {
  92. 		int l = rnd() % n + 1, r = rnd() % n + 1;
  93. 		if (l > r) {
  94. 			swap(l, r);
  95. 		}
  96. 		qry[i].l = l; qry[i].r = r;
  97. 		qry[i].idx = i;
  98. 	}
  99.  
  100. 	int64_t ans = 0;
  101. 	vector<int64_t> res(m);
  102. 	vector<int64_t> cnt((int)2e6, 0);
  103. 	sort(qry.begin(), qry.end());
  104. 	int l = 0, r = 1;
  105. 	ans = (p[1] == k);
  106. 	cnt[p[0]]++; cnt[p[1]]++;
  107.  
  108. 	for (Query q: qry) {
  109. 		q.l--;
  110. 		while (l > q.l) {
  111. 			l--;
  112. 			ans += cnt[p[l] ^ k];
  113. 			cnt[p[l]]++;
  114. 		}
  115. 		while (r < q.r) {
  116. 			r++;
  117. 			ans += cnt[p[r] ^ k];
  118. 			cnt[p[r]]++;
  119. 		}
  120. 		while (l < q.l) {
  121. 			cnt[p[l]]--;
  122. 			ans -= cnt[p[l] ^ k];
  123. 			l++;
  124. 		}
  125. 		while (r > q.r) {
  126. 			cnt[p[r]]--;
  127. 			ans -= cnt[p[r] ^ k];
  128. 			r--;
  129. 		}
  130. 		res[q.idx] = ans;
  131. 	}
  132.  
  133. 	uint64_t rhsh = 0;
  134. 	for (int i = 0; i < m; i++) {
  135. 		rhsh *= (uint64_t)1e9 + 7;
  136. 		rhsh += (uint64_t)res[i];
  137. 	}
  138. 	cout << rhsh << "\n";
  139.  
  140. 	return 0;
  141. }
Success #stdin #stdout 2.46s 15240KB
comments (?)
stdin
copy 
400000 400000
stdout
copy 
18318053225040230409
https://ideone.com/cBBIK0
language:
C++14 (gcc 8.3)
created:
5 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!