Submission #3461155


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T,size_t X>
struct BinaryTrie{
  struct Node{
    bool f;
    size_t cnt;
    Node *p,*l,*r;
    Node(){}
    Node(bool f,Node* p):f(f),cnt(0),p(p){l=r=nullptr;}
  };
  
  T acc;
  Node *root;
  BinaryTrie():acc(0){root=emplace(0,nullptr);}
  
  inline Node* emplace(bool f,Node* p){
    return new Node(f,p);
  }

  inline size_t count(Node* a){
    return a?a->cnt:0;
  }
  
  void add(const T b,size_t k=1){
    const T nb=b^acc;
    Node* a=root;
    for(int i=X-1;i>=0;i--){
      bool f=(nb>>i)&1;
      if(!f&&!a->l) a->l=emplace(f,a);
      if( f&&!a->r) a->r=emplace(f,a);
      a=f?a->r:a->l;
    }
    a->cnt+=k;    
    while((a=a->p)) a->cnt=count(a->l)+count(a->r);    
  }

  inline void update(const T b){acc^=b;}

  Node* find(const T b){
    const T nb=b^acc;
    Node* a=root;
    for(int i=X-1;i>=0;i--){
      bool f=(nb>>i)&1;
      a=f?a->r:a->l;
      if(!a) return a;
    }
    return a;
  }

  Node* check(Node *a){
    if(!a||count(a)) return a;
    delete(a);
    return nullptr;
  }

  void sub(Node* a,size_t k=1){
    assert(a&&a->cnt>=k);
    a->cnt-=k;
    while((a=a->p)){
      a->l=check(a->l);
      a->r=check(a->r);
      a->cnt=count(a->l)+count(a->r);
    }
  }
  
  Node* xmax(const T b){
    assert(count(root));
    const T nb=b^acc;
    Node* a=root;    
    for(int i=X-1;i>=0;i--){
      bool f=(~nb>>i)&1;
      a=(f&&a->r)?a->r:a->l;
    }
    return a;
  }

  int xmin(const T b){
    return xmax(~b&((T(1)<<X)-1));
  }

  Node* ge(Node *a){
    if(a&&(a->r||a->l)) return a->l?a->l:a->r;
    return a;
  }
  
  Node* next(Node* a){
    while(a->p){
      if(a->p->l==a) return ge(a->p->r);
      a=a->p;
    }
    return nullptr;
  }
  
  Node* lower_bound(const T b){
    const T nb=b^acc;
    Node* a=root;
    for(int i=X-1;i>=0;i--){
      bool f=(nb>>i)&1;
      if(!f&&a->l){a=a->l;continue;}
      if( f&&a->r){a=a->r;continue;}
      if(f) return next(a);
      return ge(a->r);
    }
    return a;
  }

  int upper_bound(const T b){
    return lower_bound(b+1);
  }
  
  T val(Node* a){
    T res(0);
    for(int i=0;i<X;i++){
      res|=T(a->f)<<i;      
      a=a->p;
    }
    return res^acc;
  }

  Node* find_by_order(size_t k){
    Node *a=root;
    if(count(a)<=k) return nullptr;
    for(int i=X-1;i>=0;i--){
      bool f=(acc>>i)&1;
      if(count(f?a->r:a->r)<=k){
        k-=count(f?a->r:a->r);
        a=f?a->l:a->r;
      }else{
        a=f?a->r:a->r;
      }
    }
    return a;
  }

  size_t order_of_key(const T b){
    const T nb=b^acc;
    Node *a=root;
    size_t res;
    for(int i=X-1;i>=0;i--){
      bool f=(nb>>i)&1;
      if(f) res+=count(a->l);      
      a=f?a->r:a->l;
      if(!a) break;
    }
    return res;
  }
};
//END CUT HERE
signed JAG2013SUMMERWARMINGUP_F(){
  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];
  using BT = BinaryTrie<int, 30>;
  BT bt;
  //map<BT::Node*, int> r;
  bt.add(0);
  //r[bt.find(0)]=0;
  int ans=-1,idx=-1,idy=-1;
  for(int i=0;i<n;i++){
    //int k=r[bt.xmax(a[i])];
    int k=0;
    int res=s[i+1]^s[k];
    if(ans<res||(ans==res&&idx>k)){
      ans=res;
      idx=k;
      idy=i;
    }
    bt.update(a[i]);
    bt.add(0);
    //if(!r.count(bt.find(0))) r[bt.find(0)]=i+1;
  }
  cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
  return 0;
}
/*
  verified on 2018/10/24
  https://beta.atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_f
*/
signed main(){
  JAG2013SUMMERWARMINGUP_F();
  return 0;
}

Submission Info

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

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 8
WA × 23
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 WA 1 ms 256 KB
10 WA 2 ms 640 KB
11 WA 2 ms 640 KB
12 WA 1 ms 384 KB
13 WA 6 ms 2688 KB
14 WA 8 ms 2944 KB
15 WA 9 ms 3584 KB
16 WA 43 ms 9856 KB
17 WA 28 ms 9472 KB
18 WA 88 ms 22272 KB
19 AC 1 ms 256 KB
2 AC 1 ms 256 KB
20 WA 1 ms 256 KB
21 AC 1 ms 256 KB
22 WA 1 ms 256 KB
23 WA 1 ms 256 KB
24 WA 1 ms 256 KB
25 WA 3 ms 768 KB
26 WA 2 ms 512 KB
27 AC 6 ms 1152 KB
28 WA 56 ms 13824 KB
29 WA 62 ms 14848 KB
3 AC 1 ms 256 KB
30 WA 38 ms 10112 KB
31 WA 79 ms 15872 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 WA 1 ms 256 KB
7 WA 1 ms 256 KB
8 AC 1 ms 256 KB
9 WA 2 ms 512 KB