#include <bits/stdc++.h>
using namespace std;
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
typedef pair < int ,int > pii;
typedef long long ll;
const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 250001;
int F[N << 4], S = 1, mx[N << 4], mn[N << 4], t, n, m, x, y, z, a[N], b[N], way[N << 4][2];
void insert(int x, int index) {
int node = 1;
ROF(i, 29, 0) {
int t = (1 << i) & x;
t = t != 0;
if(!way[node][t]) way[node][t] = ++S;
node = way[node][t];
} F[node] = max(F[node], index);
}
pii dfs(int node) {
if(way[node][0]) {
pii temp = dfs(way[node][0]);
mx[node] = max(mx[node], temp.st);
}
if(way[node][1]) {
pii temp = dfs(way[node][1]);
mx[node] = max(mx[node], temp.st);
}
if(mx[node] == 0)
mx[node] = mn[node] = F[node];
return mp(mx[node], mn[node]);
}
int solve(int node, int d, int y) {
if(d == 0) return mx[node];
if((x & (1 << d)) && (y & (1 << d))) {
if(way[node][0]) return solve(way[node][0], d-1, y);
else return 0;
}
if(y & (1 << d)) {
if(way[node][1]) return max(solve(way[node][1], d-1, y), mx[way[node][0]]);
else return mx[way[node][0]];
}
if(x & (1 << d)) {
if(way[node][1]) return solve(way[node][1], d-1, y);
else return 0;
}
if(way[node][0])
return max(way[node][1], solve(way[node][0], d-1, y));
else return mx[way[node][1]];
}
int main() {
scanf("%d %d",&n, &x);
FOR(i, 1, n) {
scanf("%d", &a[i]);
b[i] = a[i] ^ b[i-1];
insert(b[i], i);
}
dfs(1);
FOR(i, 1, n) {
t = max(t, solve(1, 29, b[i]) - i);
}
FOR(i, 0, n-t)
if((b[i+t] ^ b[i]) >= x) {
cout << i + 1 << ' ' << t << endl;
return 0;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
81800 KB |
Output is correct |
2 |
Correct |
0 ms |
81800 KB |
Output is correct |
3 |
Correct |
0 ms |
81800 KB |
Output is correct |
4 |
Correct |
2 ms |
81800 KB |
Output is correct |
5 |
Correct |
7 ms |
81800 KB |
Output is correct |
6 |
Correct |
10 ms |
81800 KB |
Output is correct |
7 |
Correct |
11 ms |
81800 KB |
Output is correct |
8 |
Correct |
12 ms |
81800 KB |
Output is correct |
9 |
Correct |
43 ms |
81800 KB |
Output is correct |
10 |
Correct |
54 ms |
81800 KB |
Output is correct |
11 |
Correct |
61 ms |
81800 KB |
Output is correct |
12 |
Correct |
52 ms |
81800 KB |
Output is correct |
13 |
Correct |
45 ms |
81800 KB |
Output is correct |
14 |
Correct |
42 ms |
81800 KB |
Output is correct |
15 |
Correct |
59 ms |
81800 KB |
Output is correct |
16 |
Correct |
35 ms |
81800 KB |
Output is correct |
17 |
Correct |
104 ms |
81800 KB |
Output is correct |
18 |
Correct |
152 ms |
81800 KB |
Output is correct |
19 |
Correct |
120 ms |
81800 KB |
Output is correct |
20 |
Correct |
157 ms |
81800 KB |
Output is correct |