Submission #3464532


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{
    size_t cnt;
    Node *p,*l,*r;
    Node(Node* p):cnt(0),p(p){l=r=nullptr;}
  };
  
  T acc;
  Node *root;
  BinaryTrie():acc(0){root=emplace(nullptr);}

  void dfs(Node *a){
    if(!a) return;
    dfs(a->l);dfs(a->r);
    delete(a);
  }
  
  inline Node* emplace(Node* p){
    return new Node(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(a);
      if( f&&!a->r) a->r=emplace(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;
      if(!a->l||!a->r) a=a->l?a->l:a->r;
      else a=f?a->l:a->r;
    }
    return a;
  }

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

  Node* ge(Node *a,int i){
    if(!a) return a;
    Node *l=a->l,*r=a->r;
    if((acc>>i)&1) swap(l,r);
    if(l||r) return ge(l?l:r,i+1);
    return a;
  }
  
  Node* next(Node* a,int i){
    if(!(a->p)) return nullptr;
    Node *l=a->p->l,*r=a->p->r;
    if((acc>>(i+1))&1) swap(l,r);
    if(a==l&&r) return ge(r,i);
    return next(a->p,i+1);
  }
  
  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((b>>i)&1) return next(a,i);
      return ge(a,i);
    }
    return a;
  }

  Node* upper_bound(const T b){
    return lower_bound(b+1);
  }
  
  T val(Node* a){
    T res(0);
    for(int i=0;i<(int)X;i++){
      assert(a->p);
      res|=(T(a==a->p->r)<<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->l)<=k){
        k-=count(f?a->r:a->l);
        a=f?a->l:a->r;
      }else{
        a=f?a->r:a->l;
      }
    }
    return a;
  }
  
  size_t order_of_key(const T b){
    Node *a=root;
    size_t res=0;
    for(int i=X-1;i>=0;i--){      
      Node *l=a->l,*r=a->r;
      if((acc>>i)&1) swap(l,r);
      bool f=(b>>i)&1;
      if(f) res+=count(l); 
      a=f?r:l;
      if(!a) break;
    }
    return res;
  }
};
//END CUT HERE

signed JAG2013SUMMERWARMINGUP_F(){
  int n;
  scanf("%d",&n);
  vector<int> a(n);
  for(int i=0;i<n;i++) scanf("%d",&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;
  using ull = unsigned long long;
  map<ull, int> r;
  bt.add(0);
  r[(ull)bt.find(0)]=0;
  int ans=-1,idx=-1,idy=-1;
  for(int i=0;i<n;i++){
    int k=r[(ull)bt.xmax(a[i])];
    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((ull)bt.find(0))) r[(ull)bt.find(0)]=i+1;
  }
  printf("%d %d %d\n",ans,idx+1,idy+1);
  return 0;
}
/*
  verified on 2018/10/24
  https://beta.atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_f
*/

signed ARC033_C(){
  int q;
  scanf("%d",&q);
  BinaryTrie<int, 30> bt;
  while(q--){
    int t,x;
    scanf("%d %d",&t,&x);
    if(t==1) bt.add(x);
    if(t==2){
      auto k=bt.find_by_order(x-1);
      printf("%d\n",bt.val(k));
      bt.sub(k);
    }
  }
  return 0;
}

/*
  verified on 2018/10/24
  https://beta.atcoder.jp/contests/arc033/tasks/arc033_3
*/

signed AOJ_DSL2B(){
  int n,q;
  scanf("%d %d",&n,&q);
  BinaryTrie<int, 30> bt;
  for(int i=0;i<q;i++){
    int c,x,y;
    scanf("%d %d %d",&c,&x,&y);
    if(c) printf("%zd\n",bt.order_of_key(y+1)-bt.order_of_key(x));
    else bt.add(x,y);
  }
  return 0;
}

/*
  verified on 2018/10/24
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp
*/

signed CFR470_C(){
  int n;
  scanf("%d",&n);
  vector<int> a(n),p(n);
  for(Int i=0;i<n;i++) scanf("%d",&a[i]);
  for(Int i=0;i<n;i++) scanf("%d",&p[i]);

  BinaryTrie<int, 30> bt;
  for(int i=0;i<n;i++) bt.add(p[i]);
  
  for(Int i=0;i<n;i++){
    if(i) printf(" ");
    auto k=bt.xmin(a[i]);
    printf("%d",a[i]^bt.val(k));
    bt.sub(k);
  }
  puts("");
  return 0;
}
/*
  verified on 2018/10/24
  http://codeforces.com/contest/947/problem/C
*/

signed CFR477_C(){
  Int n;
  scanf("%lld",&n);
  vector<Int> b(n);
  for(Int i=0;i<n;i++) scanf("%lld",&b[i]);
  
  BinaryTrie<Int, 61> bt;
  for(Int i=0;i<n;i++) bt.add(b[i]);
  
  Int z=0;
  auto apply=[&](Int a){
               z^=a;
               bt.update(a);
             };

  vector<Int> ans;
  Int x=bt.val(bt.xmin(0));
  
  ans.emplace_back(x);
  bt.sub(bt.find(x));
  apply(x);

  for(Int i=1;i<n;i++){
    if(bt.val(bt.xmax(0))<=x){
      printf("No\n");
      return 0; 
    }
    auto nxt=bt.upper_bound(x);
    //if(nxt==nullptr) exit(0);
    Int y=bt.val(nxt);
    
    ans.emplace_back(y^z);
    bt.sub(nxt);
    apply(x^y);
    x=y;    
  }
  
  printf("Yes\n");
  for(Int i=0;i<n;i++){
    if(i) printf(" ");
    printf("%lld",ans[i]);
  }
  puts("");
  return 0;
}
/*
  verified on 2018/10/24
  http://codeforces.com/contest/966/problem/C
*/


struct HLDecomposition {
  int n,pos;
  vector<vector<int> > G;
  vector<int> vid, head, sub, par, dep, inv, type;
  
  HLDecomposition(){}
  HLDecomposition(int n):
    n(n),pos(0),G(n),vid(n,-1),head(n),sub(n,1),
    par(n,-1),dep(n,0),inv(n),type(n){}
  
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void build(vector<int> rs={0}) {
    int c=0;
    for(int r:rs){
      dfs_sz(r);
      head[r]=r;
      dfs_hld(r,c++);
    }
  }
  
  void dfs_sz(int v) {
    for(int &u:G[v]){
      if(u==par[v]) continue;
      par[u]=v;
      dep[u]=dep[v]+1;
      dfs_sz(u);      
      sub[v]+=sub[u];      
      if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]);
    }
  }

  void dfs_hld(int v,int c) {
    vid[v]=pos++;
    inv[vid[v]]=v;
    type[v]=c;
    for(int u:G[v]){
      if(u==par[v]) continue;
      head[u]=(u==G[v][0]?head[v]:u);
      dfs_hld(u,c);
    }    
  }
  
  int lca(int u,int v){
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]==head[v]) return u;
      v=par[head[v]];
    }
  }
  
  Int la(Int v,Int k){
    while(1){
      Int u=head[v];
      if(vid[v]-k>=vid[u]) return inv[vid[v]-k];
      k-=vid[v]-vid[u]+1;
      v=par[u];
    }
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
  }
};

//INSERT ABOVE HERE
signed KUPC2018_M(){
  using ll = long long;
  int n;
  scanf("%d",&n);
  HLDecomposition hld(n);
  for(int i=1;i<n;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    a--;b--;
    hld.add_edge(a,b);
  }
  hld.build();

  using T = BinaryTrie<int, 31>;
  using E = pair<int, ll>;

  struct SegmentTree{
    int n;
    vector<T> dat;
    SegmentTree(int n_){
      n=1;
      while(n<n_) n<<=1;
      dat=vector<T>(n*2);
      for(int i=0;i<n*2;i++) dat[i]=T();
    }
    void reset(){
      for(int i=0;i<n*2;i++) dat[i].dfs(dat[i].root);
    }
    void update(int a,int b,E x){
      for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1){
        if(l&1) dat[l++].add(x.first,x.second);
        if(r&1) dat[--r].add(x.first,x.second);
      }
    }
    ll query(int k,E x){
      ll res=0;
      k+=n;
      while(k){
        dat[k].update(x.first);
        res+=dat[k].order_of_key(x.second+1);
        dat[k].update(x.first);
        k>>=1;
      }
      return res;
    }
  };
  
  int q;
  scanf("%d",&q);

  vector<int> type(q),vs(q),xs(q),ks(q),ys(q),zs(q);
  vector<ll> ans(q);
  for(int i=0;i<q;i++){
    scanf("%d",&type[i]);
    if(type[i]==1) scanf("%d %d %d",&vs[i],&xs[i],&ks[i]);      
    if(type[i]==2) scanf("%d %d %d",&vs[i],&ys[i],&zs[i]);
    if(type[i]==3) scanf("%d",&vs[i]);
    vs[i]--;
  }
  
  const int UKU = 8;
  for(int uku=0;uku<UKU;uku++){
    SegmentTree seg(n);
    int rt=0;
    for(int i=0;i<q;i++){
      if(type[i]==1&&(i%UKU)==uku){
        int v=vs[i],x=xs[i],k=ks[i];
        if(rt==v){	
          seg.update(0,n,E(x,k));
        }else if(hld.lca(rt,v)==v){
          int u=hld.la(rt,hld.distance(rt,v)-1);
          int l=hld.vid[u],r=hld.vid[u]+hld.sub[u];
          seg.update(0,l,E(x,k));
          seg.update(r,n,E(x,k));
        }else{	
          int l=hld.vid[v],r=hld.vid[v]+hld.sub[v];
          seg.update(l,r,E(x,k));
        }
      }
      if(type[i]==2){
        int v=vs[i],y=ys[i],z=zs[i];
        ans[i]+=seg.query(hld.vid[v],E(y,z));
      }
      if(type[i]==3){
        rt=vs[i];
      }
    }
    seg.reset();
  }
  
  for(int i=0;i<q;i++)
    if(type[i]==2) printf("%lld\n",ans[i]);
  return 0;
}

signed main(){
  JAG2013SUMMERWARMINGUP_F();
  //ARC033_C();
  //AOJ_DSL2B();
  //CFR470_C();
  //CFR477_C();
  //KUPC2018_M();
  return 0;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User beet
Language C++14 (GCC 5.4.1)
Score 100
Code Size 10002 Byte
Status AC
Exec Time 174 ms
Memory 28288 KB

Compile Error

./Main.cpp: In function ‘int JAG2013SUMMERWARMINGUP_F()’:
./Main.cpp:165:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:167:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<n;i++) scanf("%d",&a[i]);
                                         ^
./Main.cpp: In function ‘int ARC033_C()’:
./Main.cpp:198:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
                 ^
./Main.cpp:202:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&t,&x);
                         ^
./Main.cpp: In function ‘int AOJ_DSL2B()’:
./Main.cpp:220:23: warning: ignoring return value of ‘int scanf(const char*, ...)...

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 31
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 768 KB
11 AC 2 ms 640 KB
12 AC 2 ms 512 KB
13 AC 9 ms 2944 KB
14 AC 11 ms 3456 KB
15 AC 12 ms 4096 KB
16 AC 76 ms 13056 KB
17 AC 45 ms 11392 KB
18 AC 174 ms 28288 KB
19 AC 1 ms 256 KB
2 AC 1 ms 256 KB
20 AC 1 ms 256 KB
21 AC 1 ms 256 KB
22 AC 1 ms 256 KB
23 AC 1 ms 256 KB
24 AC 1 ms 256 KB
25 AC 4 ms 1024 KB
26 AC 2 ms 640 KB
27 AC 8 ms 1536 KB
28 AC 98 ms 17792 KB
29 AC 109 ms 19200 KB
3 AC 1 ms 256 KB
30 AC 64 ms 12800 KB
31 AC 143 ms 21376 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 AC 1 ms 256 KB
7 AC 1 ms 256 KB
8 AC 1 ms 256 KB
9 AC 2 ms 640 KB