Submission #2182896


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
template<typename T,int X>
struct BinaryTrie{
  struct Node{
    bool f;
    T laz;
    int par,idx,cnt,nxt[2];
    Node(bool f,int par):
      f(f),laz(0),par(par),idx(-1),cnt(0){nxt[0]=nxt[1]=-1;}
  };

  vector<Node> v;
  BinaryTrie(){v.emplace_back(0,-1);}

  inline int count(int x){
    return x<0?0:v[x].cnt;
  }

  inline void eval(int i,int x){
    if((v[x].laz>>i)&1){
      swap(v[x].nxt[0],v[x].nxt[1]);
      v[x].laz^=T(1)<<i;
    }
    for(int k=0;k<2;k++){
      if(!~v[x].nxt[k]) continue;
      v[v[x].nxt[k]].laz^=v[x].laz;
      v[v[x].nxt[k]].f=k;
    }
    v[x].laz=0;
  }
  
  void add(const T b,int x){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(b>>i)&1;
      if(~v[pos].nxt[f]){
	pos=v[pos].nxt[f];
	continue;
      }
      int npos=v.size();
      v[pos].nxt[f]=npos;
      v.emplace_back(f,pos);
      pos=npos;
    }
    if(!~v[pos].idx) v[pos].idx=x;
    v[pos].cnt++;
    for(int i=0;i<X;i++){
      pos=v[pos].par;
      v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
    }
  }

  void update(const T b){
    v[0].laz^=b;
  }

  int find(const T b){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(b>>i)&1;
      if(~v[pos].nxt[f]) pos=v[pos].nxt[f];
      else return -1;
    }
    return pos;
  }
  
  int xmax(const T b){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(~b>>i)&1;
      f^=!~v[pos].nxt[f];
      pos=v[pos].nxt[f];
    }
    return v[pos].idx;
  }

  int xmin(const T b){
    return xmax(~b&((T(1)<<X)-1));
  }
  
};
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  vector<int> s(n+1,0);
  for(int i=0;i<n;i++) s[i+1]=s[i]^a[i];
  BinaryTrie<int, 30> bt;
  bt.add(0,0);
  int ans=-1,idx=-1,idy=-1;
  for(int i=0;i<n;i++){
    int k=bt.xmax(a[i]);
    int res=s[i+1]^s[k];
    if(ans<res){
      ans=res;
      idx=k;
      idy=i;
    }
    bt.update(a[i]);
    bt.add(0,i+1);
  }
  cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
  return 0;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User beet
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2227 Byte
Status WA
Exec Time 124 ms
Memory 17004 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 21
WA × 10
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 1 ms 256 KB
10 AC 2 ms 800 KB
11 AC 2 ms 640 KB
12 AC 2 ms 640 KB
13 AC 9 ms 2168 KB
14 WA 11 ms 2168 KB
15 AC 12 ms 4724 KB
16 WA 65 ms 8176 KB
17 WA 38 ms 8304 KB
18 WA 124 ms 17004 KB
19 WA 1 ms 256 KB
2 AC 1 ms 256 KB
20 AC 1 ms 256 KB
21 AC 1 ms 256 KB
22 WA 2 ms 256 KB
23 AC 1 ms 256 KB
24 AC 2 ms 256 KB
25 AC 5 ms 800 KB
26 WA 3 ms 640 KB
27 WA 10 ms 1340 KB
28 AC 84 ms 15596 KB
29 WA 92 ms 17004 KB
3 AC 1 ms 256 KB
30 AC 59 ms 9712 KB
31 WA 124 ms 16492 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 AC 1 ms 256 KB
7 AC 1 ms 384 KB
8 AC 1 ms 256 KB
9 AC 2 ms 640 KB