Submission #1035975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035975		pera	XOR (IZhO12_xor)	C++17	0 / 100	64 ms	83544 KiB

xor

#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; 
} 

• Subtask 1: 0 / 100