pypcdev

Untitled

Sep 15th, 2021
547
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. #define int ll
  6. #define fi first
  7. #define se second
  8. #define ins insert
  9. #define er erase
  10. #define pb push_back
  11. #define ppb pop_back
  12. #define pf push_front
  13. #define ppf pop_front
  14. #define INF (ll)1e18
  15.  
  16. struct node{
  17.     node*son[2]={};
  18.     int all=0;
  19.     int term=0;
  20. };
  21.  
  22.  
  23. typedef node*pnode;
  24. pnode root=new node;
  25. const int NMAX=1e6;
  26. int nm[NMAX+1];
  27. map<int,int>f;
  28.  
  29. int check(int n){
  30.     pnode v=root;
  31.     if(!(v->all))return -1;
  32.     int ans=0;
  33.     for(int k=60;k>=0;k--){
  34.         int c=(n>>k)&1ll;
  35.         if(!(v->son[c])||!(v->son[c]->all))c^=1;
  36.         v=v->son[c];
  37.         ans|=(c<<k);
  38.     }
  39.     return f[ans];
  40. }
  41.  
  42. void add(int n){
  43.     pnode v=root;
  44.     for(int k=60;k>=0;k--){
  45.         v->all++;
  46.         int c=(n>>k)&1ll;
  47.         if(!(v->son[c]))v->son[c]=new node;
  48.         v=v->son[c];
  49.     }
  50.     v->all++;
  51.     v->term++;
  52. }
  53.  
  54. void del(int n){
  55.     pnode v=root;
  56.     for(int k=60;k>=0;k--){
  57.         int c=(n>>k)&1ll;
  58.         v->all--;
  59.         v=v->son[c];
  60.     }
  61.     v->all--;
  62.     v->term--;
  63. }
  64.  
  65. signed main(){
  66.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  67.     int q;
  68.     cin>>q;
  69.     for(int i=1;i<=q;i++){
  70.         char r;int v;
  71.         cin>>r>>v;
  72.         if(r=='+'){
  73.             cout<<check(v)<<"\n";
  74.             add(v);
  75.             nm[i]=v;
  76.             f[v]+=i;
  77.         }else{
  78.             del(nm[v]);
  79.             f[nm[v]]-=v;
  80.             cout<<check(nm[v])<<"\n";
  81.         }
  82.     }
  83. }
RAW Paste Data