# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1035975 |
2024-07-26T22:39:08 Z |
pera |
XOR (IZhO12_xor) |
C++17 |
|
64 ms |
83544 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 250000 + 1 , LOG = 3;
int n , x , T = 0;
map<int , int> POS;
vector<int> p(N);
vector<vector<int>> t(N * LOG , vector<int>(2)) , mx(N * LOG , vector<int>(2));
void UPD(int u , int e){
int v = 0;
for(int bit = LOG - 1;bit >= 0;bit --){
if(!t[v][u >> bit & 1]){
t[v][u >> bit & 1] = ++T;
mx[v][u >> bit & 1] = e;
}
v = t[v][u >> bit & 1];
}
}
int GET(int u){
int v = 0 , s = -1;
for(int bit = LOG - 1;bit >= 0;bit --){
int _u = u >> bit & 1;
int _x = v >> bit & 1;
if(_x){
v = t[v][_u ^ 1];
if(v == 0){
return s;
}
continue;
}
s = max(s , mx[v][_u ^ 1]);
v = t[v][_u];
}
return max(s , POS[u ^ x]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> x;
for(int i = 1;i <= n;i ++){
int x;
cin >> x;
p[i] = p[i - 1] ^ x;
}
int L = -1 , R = -1;
for(int i = n;i >= 0;i --){
int r = GET(p[i]);
if(i < r && r <= n && (p[r] ^ p[i]) >= x){
if(r - i > R - L + 1){
L = i + 1;
R = r;
}
}
UPD(p[i] , i);
if(POS.find(p[i]) == POS.end()){
POS[p[i]] = i;
}
}
cout << L << " " << R - L + 1 << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
83544 KB |
Output is correct |
2 |
Correct |
63 ms |
83508 KB |
Output is correct |
3 |
Incorrect |
60 ms |
83536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |