fork(1) 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. inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
  62. 	if (pow == 0) {
  63. 		return 0;
  64. 	}
  65. 	int hpow = 1 << (pow-1);
  66. 	int seg = (x < hpow) ? (
  67. 		(y < hpow) ? 0 : 3
  68. 	) : (
  69. 		(y < hpow) ? 1 : 2
  70. 	);
  71. 	seg = (seg + rotate) & 3;
  72. 	const int rotateDelta[4] = {3, 0, 0, 1};
  73. 	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  74. 	int nrot = (rotate + rotateDelta[seg]) & 3;
  75. 	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
  76. 	int64_t ans = seg * subSquareSize;
  77. 	int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
  78. 	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  79. 	return ans;
  80. }
  81.  
  82. struct Query {
  83. 	int l, r, idx;
  84. 	int64_t ord;
  85.  
  86. 	inline void calcOrder() {
  87. 		ord = gilbertOrder(l, r, 21, 0);
  88. 	}
  89. };
  90.  
  91. inline bool operator<(const Query &a, const Query &b) {
  92. 	return a.ord < b.ord;
  93. }
  94.  
  95. signed main() {
  96. 	#ifndef USE_FILE_IO
  97. 		ios_base::sync_with_stdio(false);
  98. 	#endif
  99.  
  100. 	mt19937 rnd(42);
  101.  
  102. 	int n, m, k; cin >> n >> m; k = rnd() % 1048576;
  103. 	vector<int> p(n+1);
  104. 	for (int i = 0; i < n; i++) {
  105. 		int val = rnd() % 1048576;
  106. 		p[i+1] = p[i] ^ val;
  107. 	}
  108.  
  109. 	vector<Query> qry(m);
  110. 	for (int i = 0; i < m; i++) {
  111. 		int l = rnd() % n + 1, r = rnd() % n + 1;
  112. 		if (l > r) {
  113. 			swap(l, r);
  114. 		}
  115. 		qry[i].l = l; qry[i].r = r;
  116. 		qry[i].idx = i;
  117. 		qry[i].calcOrder();
  118. 	}
  119.  
  120. 	int64_t ans = 0;
  121. 	vector<int64_t> res(m);
  122. 	vector<int64_t> cnt((int)2e6, 0);
  123. 	sort(qry.begin(), qry.end());
  124. 	int l = 0, r = 1;
  125. 	ans = (p[1] == k);
  126. 	cnt[p[0]]++; cnt[p[1]]++;
  127.  
  128. 	for (Query q: qry) {
  129. 		while (l > q.l) {
  130. 			l--;
  131. 			ans += cnt[p[l] ^ k];
  132. 			cnt[p[l]]++;
  133. 		}
  134. 		while (r < q.r) {
  135. 			r++;
  136. 			ans += cnt[p[r] ^ k];
  137. 			cnt[p[r]]++;
  138. 		}
  139. 		while (l < q.l) {
  140. 			cnt[p[l]]--;
  141. 			ans -= cnt[p[l] ^ k];
  142. 			l++;
  143. 		}
  144. 		while (r > q.r) {
  145. 			cnt[p[r]]--;
  146. 			ans -= cnt[p[r] ^ k];
  147. 			r--;
  148. 		}
  149. 		res[q.idx] = ans;
  150. 	}
  151.  
  152. 	uint64_t rhsh = 0;
  153. 	for (int i = 0; i < m; i++) {
  154. 		rhsh *= (uint64_t)1e9 + 7;
  155. 		rhsh += (uint64_t)res[i];
  156. 	}
  157. 	cout << rhsh << "\n";
  158.  
  159. 	return 0;
  160. }
  161.  
  162.  
Success #stdin #stdout 2.46s 32564KB
comments (?)
stdin
copy 
400000 400000
stdout
copy 
4675657410287817021
https://ideone.com/WZfHWs
language:
C++14 (gcc 8.3)
created:
6 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!