#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=3e5+5;
const int B = 31;
int n,x,sz = 1;
int dp[maxn * B];
int to[maxn * B][2];
void add(int v,int idx){
int now = 0;
dp[0] = min(dp[0],idx);
for(int i = B-1;i >= 0;i--){
int xx = (v >> i) & 1;
if(!to[now][xx]) to[now][xx] = sz++;
now = to[now][xx];
dp[now] = min(dp[now],idx);
}
}
int tap(int v){
int now = 0;
int cp = 1e9;
bool tr = 1;
for(int i = B-1;i >= 0;i--){
int a = (v >> i) & 1;
int b = (x >> i) & 1;
if(!b and to[now][a ^ 1]) cp = min(cp,dp[to[now][a^1]]);
if(to[now][a ^ b]) now = to[now][a^b];
else {
tr = 0;
break;
}
}
if(tr) cp = min(cp,dp[now]);
return cp;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> x;
memset(dp, 127, sizeof dp);
int nw = 0;
int ans = 0;
int ii = -1,k = -1;
add(0,0);
for(int i = 1;i <= n;i++){
int a; cin >> a;
nw ^= a;
add(nw,i);
int ind = tap(nw);
if(ans < i - ind){
ans = i - ind;
ii = ind + 1;
k = i + 1 - ii;
}
}
cout<<ii<<' '<<k;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
36684 KB |
Output is correct |
2 |
Correct |
16 ms |
36652 KB |
Output is correct |
3 |
Correct |
20 ms |
36648 KB |
Output is correct |
4 |
Correct |
16 ms |
36676 KB |
Output is correct |
5 |
Correct |
21 ms |
37064 KB |
Output is correct |
6 |
Correct |
22 ms |
37204 KB |
Output is correct |
7 |
Correct |
22 ms |
37192 KB |
Output is correct |
8 |
Correct |
23 ms |
37416 KB |
Output is correct |
9 |
Correct |
53 ms |
44124 KB |
Output is correct |
10 |
Correct |
67 ms |
44112 KB |
Output is correct |
11 |
Correct |
69 ms |
43988 KB |
Output is correct |
12 |
Correct |
53 ms |
44060 KB |
Output is correct |
13 |
Correct |
53 ms |
44104 KB |
Output is correct |
14 |
Correct |
48 ms |
44108 KB |
Output is correct |
15 |
Correct |
61 ms |
44068 KB |
Output is correct |
16 |
Correct |
62 ms |
44040 KB |
Output is correct |
17 |
Correct |
146 ms |
52692 KB |
Output is correct |
18 |
Correct |
140 ms |
52632 KB |
Output is correct |
19 |
Correct |
142 ms |
52680 KB |
Output is correct |
20 |
Correct |
141 ms |
52640 KB |
Output is correct |