#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int t,aft[32*N][2],mn[32*N],id,a,n;
void add(int x,int ind) {
int u = 0;
for(int i=32;i>=0;i--) {
int b = ((1ll<<i)&x ? 1 : 0);
if(!aft[u][b]) {
id++;
mn[id] = ind;
aft[u][b] = id;
}
u = aft[u][b];
}
}
int get(int x) {
int ans = n + 1,u = 0;
for(int i=32;i>=0;i--) {
int b = ((1ll<<i)&x ? 1 : 0);
if(!((1ll<<i) & a)) {
ans = min(ans,mn[aft[u][1-b]]);
if(!aft[u][b]) return ans;
u = aft[u][b];
continue;
}
if(!aft[u][1-b]) return ans;
u = aft[u][1-b];
}
ans = min(ans,mn[u]);
return ans;
}
main(){
cin >> n >> a;
mn[0] = n + 1;
int ans = 0,p = 0,ind = 0;
add(0,0);
for(int i=1;i<=n;i++) {
int b;
cin >> b;
p ^= b;
int x = i - get(p);
if(x > ans) {
ans = x;
ind = i - x + 1;
}
ans = max(ans,i - get(p));
add(p,i);
}
cout<<ind<<" "<<ans;
}
Compilation message
xor.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
37 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
13 ms |
1464 KB |
Output is correct |
6 |
Correct |
14 ms |
1540 KB |
Output is correct |
7 |
Correct |
15 ms |
1628 KB |
Output is correct |
8 |
Correct |
16 ms |
1660 KB |
Output is correct |
9 |
Correct |
72 ms |
20804 KB |
Output is correct |
10 |
Correct |
72 ms |
20972 KB |
Output is correct |
11 |
Correct |
80 ms |
20860 KB |
Output is correct |
12 |
Correct |
74 ms |
20860 KB |
Output is correct |
13 |
Correct |
76 ms |
21008 KB |
Output is correct |
14 |
Correct |
79 ms |
20916 KB |
Output is correct |
15 |
Correct |
74 ms |
20992 KB |
Output is correct |
16 |
Correct |
81 ms |
20904 KB |
Output is correct |
17 |
Correct |
209 ms |
44304 KB |
Output is correct |
18 |
Correct |
195 ms |
44296 KB |
Output is correct |
19 |
Correct |
203 ms |
44356 KB |
Output is correct |
20 |
Correct |
218 ms |
44328 KB |
Output is correct |