Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <ctime>
- #include <cstring>
- #include <deque>
- #include <cstdio>
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #include <map>
- #include <set>
- #define ll long long
- #define fname "c"
- #define F first
- #define S second
- #define mod 1000000
- #define INF 1000000000
- #define mp make_pair
- #define pb push_back
- using namespace std;
- const int N = 250500;
- int n, d[N], res, p, sz = 1, x, a[N], len, pref;
- struct vertex
- {
- int mn, nx[3], pr;
- vertex ()
- {
- mn = N + 123;
- pr = 0;
- memset (nx, 0, sizeof nx);
- }
- };
- vertex t[N * 30];
- bool have (int x, int p)
- {
- return (x >> p) & 1;
- }
- void add (int x, int p)
- {
- int v = 1;
- for (int i = 29;i >= 0;i --)
- {
- int f = have (x, i);
- if (!t[v].nx[f])
- t[v].nx[f] = ++ sz;
- t[t[v].nx[f]].pr = v;
- v = t[v].nx[f];
- }
- t[v].mn = min (t[v].mn, p);
- while (v > 1)
- {
- int u = t[v].pr;
- for (int i = 0;i < 2;i ++)
- if (t[u].nx[i])
- t[u].mn = min (t[u].mn, t[t[u].nx[i]].mn);
- v = u;
- }
- }
- int get (int k)
- {
- int res = N + 123, v = 1;
- for (int i = 29;i >= 0;i --)
- {
- int f = have (x, i);
- if (f > 0)
- {
- int d = have (k, i);
- if (t[v].nx[d ^ 1])
- v = t[v].nx[d ^ 1];
- else
- return res;
- }
- else
- {
- int d = have (k, i);
- if (t[v].nx[d ^ 1])
- res = min (res, t[t[v].nx[d ^ 1]].mn);
- if (t[v].nx[d])
- v = t[v].nx[d];
- else
- return res;
- }
- }
- // res = min (res, t[v].mn);
- return res;
- }
- int main ()
- {
- freopen (fname".in", "r", stdin);
- freopen (fname".out", "w", stdout);
- scanf ("%d%d", &n, &x);
- for (int i = 1;i <= n;i ++)
- {
- scanf ("%d", &a[i]);
- d[i] = d[i - 1] ^ a[i];
- }
- add (0, 0);
- for (int r = 1;r <= n;r ++)
- {
- int l = get (d[r]);
- if (r - l > len)
- {
- len = r - l;
- p = l + 1;
- }
- add (d[r], r);
- }
- printf ("%d %d\n", p, len);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement