Submission #1163771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163771		LmaoLmao	Klasika (COCI20_klasika)	C++17	110 / 110	1429 ms	492116 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

int d[200005];
int val[6000001];
vector<int> adj[200005];
int trie[6000001][2];
vector<int> F[6000001];
vector<int> a[6000001];
int timer = 0;
int kien=1;
int st[200005],ed[200005];
int t = 0;

void update(int n,int pos,int cur) {
  for(int i=pos;i<a[cur].size();i+=i & -i) {
    F[cur][i]++;
  }
}
int get(int pos,int cur) {
  int res=0;
  for(int i=pos;i>0;i-=i & -i) {
    res+=F[cur][i];
  }
  return res;
}

void elt(int u){
    st[u] = ++t;
    for(int v : adj[u]){
        elt(v);
    }
    ed[u] = t;
}
int getans(int x,int l,int r){
    int u = 0;
    for(int i = 30;i >= 0;i--){
       int v = (d[x] >> i)&1;
       if(!v){ 
          int posr=(upper_bound(a[trie[u][1]].begin(),a[trie[u][1]].end(),r)-a[trie[u][1]].begin())-1;
          int posl=lower_bound(a[trie[u][1]].begin(),a[trie[u][1]].end(),l)-a[trie[u][1]].begin();
          int it=get(posr,trie[u][1])-get(posl-1,trie[u][1]);
          if(it>0){
              u = trie[u][1];
          }else{
              u = trie[u][0];
          }
       }else{
          int posr=(upper_bound(a[trie[u][0]].begin(),a[trie[u][0]].end(),r)-a[trie[u][0]].begin())-1;
          int posl=lower_bound(a[trie[u][0]].begin(),a[trie[u][0]].end(),l)-a[trie[u][0]].begin();
          int it=get(posr,trie[u][0])-get(posl-1,trie[u][0]);
            if(it>0){
              u = trie[u][0];
          }else{
              u = trie[u][1];
          }
       }
    }
    return val[u] ^ d[x];
}
void add(int x){
    int u = 0;
    for(int i = 30;i >= 0;i--){
        int v = (d[x] >> i) & 1;
        if(!trie[u][v]) {
          trie[u][v] = ++timer;
        }
        u = trie[u][v];
        if(a[u].empty()) {
          a[u].push_back(0);
          F[u].push_back(0);
        }
        a[u].push_back(st[x]);
        F[u].push_back(0);
    }
    //cout << timer << ' ' << val[u] << endl;
    val[u] = d[x];
}
void add1(int x) {
    int u = 0;
    for(int i = 30;i >= 0;i--){
        int v = (d[x] >> i) & 1;
        u = trie[u][v];
        int pos=lower_bound(a[u].begin(),a[u].end(),st[x])-a[u].begin();
        update(a[u].size()-1,pos,u);
    }
}
int query[200005][3];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int q; cin >> q;
    for(int i = 1;i <= q;i++){
        string s; cin >> s;
        int x, y; cin >> x>> y;
        query[i][1] = x;
        query[i][2] = y;
        if (s == "Add"){
            query[i][0] = 0;
            d[++kien]= d[x] ^ y;
            adj[x].push_back(kien);
        }else{
            query[i][0] = 1;
        }
    }
    elt(1);
    kien = 1;
    add(kien);
    for(int i = 1;i <= q;i++){
      if(!query[i][0]){
          add(++kien);
      }
    }
    for(int i=1;i<=timer;i++) {
      sort(a[i].begin(),a[i].end());
    }
    kien=1;
    add1(kien);
    for(int i = 1;i <= q;i++){
        if(!query[i][0]){
            add1(++kien);
        }else{
            cout << getans(query[i][1],st[query[i][2]],ed[query[i][2]]) << "\n";
        }
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44