Advertisement
Guest User

Untitled

a guest
Dec 20th, 2014
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <ctime>
  4. #include <cstring>
  5. #include <deque>
  6. #include <cstdio>
  7. #include <fstream>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <queue>
  11. #include <stack>
  12. #include <vector>
  13. #include <map>
  14. #include <set>
  15. #define ll long long
  16. #define fname "c"
  17. #define F first
  18. #define S second
  19. #define mod 1000000
  20. #define INF 1000000000
  21. #define mp make_pair
  22. #define pb push_back
  23.  
  24. using namespace std;
  25.  
  26. const int N = 250500;
  27.  
  28. int n, d[N], res, p, sz = 1, x, a[N], len, pref;
  29.  
  30. struct vertex
  31. {
  32. int mn, nx[3], pr;
  33. vertex ()
  34. {
  35. mn = N + 123;
  36. pr = 0;
  37. memset (nx, 0, sizeof nx);
  38. }
  39. };
  40. vertex t[N * 30];
  41.  
  42. bool have (int x, int p)
  43. {
  44. return (x >> p) & 1;
  45. }
  46.  
  47. void add (int x, int p)
  48. {
  49. int v = 1;
  50. for (int i = 29;i >= 0;i --)
  51. {
  52. int f = have (x, i);
  53. if (!t[v].nx[f])
  54. t[v].nx[f] = ++ sz;
  55. t[t[v].nx[f]].pr = v;
  56. v = t[v].nx[f];
  57. }
  58.  
  59. t[v].mn = min (t[v].mn, p);
  60. while (v > 1)
  61. {
  62. int u = t[v].pr;
  63. for (int i = 0;i < 2;i ++)
  64. if (t[u].nx[i])
  65. t[u].mn = min (t[u].mn, t[t[u].nx[i]].mn);
  66. v = u;
  67. }
  68. }
  69.  
  70. int get (int k)
  71. {
  72. int res = N + 123, v = 1;
  73. for (int i = 29;i >= 0;i --)
  74. {
  75. int f = have (x, i);
  76. if (f > 0)
  77. {
  78. int d = have (k, i);
  79. if (t[v].nx[d ^ 1])
  80. v = t[v].nx[d ^ 1];
  81. else
  82. return res;
  83. }
  84. else
  85. {
  86. int d = have (k, i);
  87. if (t[v].nx[d ^ 1])
  88. res = min (res, t[t[v].nx[d ^ 1]].mn);
  89. if (t[v].nx[d])
  90. v = t[v].nx[d];
  91. else
  92. return res;
  93. }
  94. }
  95. // res = min (res, t[v].mn);
  96. return res;
  97. }
  98.  
  99. int main ()
  100. {
  101. freopen (fname".in", "r", stdin);
  102. freopen (fname".out", "w", stdout);
  103.  
  104. scanf ("%d%d", &n, &x);
  105. for (int i = 1;i <= n;i ++)
  106. {
  107. scanf ("%d", &a[i]);
  108. d[i] = d[i - 1] ^ a[i];
  109. }
  110.  
  111. add (0, 0);
  112.  
  113. for (int r = 1;r <= n;r ++)
  114. {
  115. int l = get (d[r]);
  116. if (r - l > len)
  117. {
  118. len = r - l;
  119. p = l + 1;
  120. }
  121. add (d[r], r);
  122. }
  123.  
  124. printf ("%d %d\n", p, len);
  125.  
  126. return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement