#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 250010;
const int mod = 1e9 + 7;
const int inf = 1e9;
int pref[N],a[N],trie[N * 31][2],mn[N * 31 * 2],idx = 0;
void Add(int x,int i) {
int node = 0;
for(int j = 30; j >= 0; j--) {
int bit = x >> j & 1;
if(!trie[node][bit]) trie[node][bit] = ++idx;
node = trie[node][bit];
mn[node] = min(mn[node],i);
}
}
int get(int tr,int x) {
int node = 0,val = 0,res = inf;
for(int j = 30; j >= 0; j--) {
int bit = x >> j & 1;
int bt = tr >> j & 1;
if(bit > 0) {
if(!trie[node][bit ^ bt]) break;
node = trie[node][bit ^ bt];
res = min(res,mn[node]);
}else {
if(trie[node][1] > 0) res = min(res,mn[trie[node][1]]);
if(!trie[node][0]) break;
node = trie[node][0];
//if(!j) res = min(res,mn[node]);
}
}
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,x;
cin >> n >> x;
for(int i = 1; i < N * 31 * 2; i++) mn[i] = inf;
int l = n + 1,r = n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = a[i] ^ pref[i - 1];
if(pref[i] >= x) {
l = 1,r = i;
}
int L = get(pref[i],x);
if(i - L + 1 > r - l + 1) {
l = L;
r = i;
}
if(i > 1) Add(pref[i - 1],i);
}
cout << l << " " << r - l + 1;
return 0;
}
Compilation message
xor.cpp: In function 'int get(int, int)':
xor.cpp:32:15: warning: unused variable 'val' [-Wunused-variable]
32 | int node = 0,val = 0,res = inf;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
31 ms |
63132 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |