fork(3) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <array>
  6. using namespace std;
  7. typedef long long ll;
  8. #define SZ(a) (int)(a).size()
  9.  
  10. const int maxp = 20;
  11.  
  12. struct Trie {
  13. 	vector<array<int,2>> t;
  14. 	Trie() {
  15. 		t.assign(1, {-1, -1});
  16. 	}
  17. 	int query(int x) {
  18. 		int ret = 0;
  19. 		int d = 0;
  20. 		for (int i = maxp-1; i >= 0; i--) {
  21. 			ret <<= 1;
  22. 			int b = x>>i & 1;
  23. 			if (t[d][b ^ 1] == -1) {
  24. 				d = t[d][b];
  25. 			}
  26. 			else {
  27. 				d = t[d][b ^ 1];
  28. 				ret++;
  29. 			}
  30. 		}
  31. 		return ret;
  32. 	}
  33. 	void insert(int x) {
  34. 		int d = 0;
  35. 		for (int i = maxp-1; i >= 0; i--) {
  36. 			int b = x>>i & 1;
  37. 			if (t[d][b] == -1) {
  38. 				t[d][b] = SZ(t);
  39. 				t.push_back({-1, -1});
  40. 			}
  41. 			d = t[d][b];
  42. 		}
  43. 	}
  44. };
  45.  
  46. struct Sg {
  47. 	int n;
  48. 	vector<Trie> t;
  49. 	Sg(int n) : n(n) {
  50. 		t.resize(2*n);
  51. 	}
  52. 	int query(int l, int r, int x) {
  53. 		int ret = 0;
  54. 		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  55. 			if (l & 1) ret = max(ret, t[l++].query(x));
  56. 			if (r & 1) ret = max(ret, t[--r].query(x));
  57. 		}
  58. 		return ret;
  59. 	}
  60. 	void insert(int i, int x) {
  61. 		for (i += n; i > 0; i >>= 1) {
  62. 			t[i].insert(x);
  63. 		}
  64. 	}
  65. };
  66.  
  67.  
  68. int main() {
  69. 	cin.sync_with_stdio(false);
  70. 	int n;
  71. 	cin >> n;
  72. 	Sg sg(n);
  73. 	for (int i = 0; i < n; i++) {
  74. 		int x;
  75. 		cin >> x;
  76. 		sg.insert(i, x);
  77. 	}
  78. 	int nq;
  79. 	cin >> nq;
  80. 	for (int iq = 0; iq < nq; iq++) {
  81. 		int l, r, x;
  82. 		cin >> l >> r >> x;
  83. 		l--;
  84. 		auto ans = sg.query(l, r, x);
  85. 		printf("%d\n", ans);
  86. 	}
  87. 	return 0;
  88. }
  89.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9ypOF4
language:
C++14 (gcc 8.3)
created:
7 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!