fork download
copy 
  1. /// vn.spoj.com/problems/ORDERSET/
  2.  
  3. /// trie bit by muoii
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 0
  9. #define maxc 0
  10. #define len 31
  11. #define oo 1000000007
  12. #define mid ((l+r)>>1)
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  15. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  16. struct trie{
  17.     int con,fin;
  18.     trie *next[2];
  19.  
  20.     int rev(int x)
  21.     {
  22.         int rv=0;
  23.         for(int i=0;i<len;i++)
  24.         {
  25.             rv<<=1;
  26.             rv|=x&1;
  27.             x>>=1;
  28.         }
  29.         return rv;
  30.     }
  31.  
  32.     void add(int x)
  33.     {
  34.         if(check(x)) return; /// with a val, only 0/1 in set
  35.         this->con++;
  36.         trie *ptr=this;
  37.  
  38.         x=rev(x);bool bit;
  39.         for(int i=0;i<len;i++)
  40.         {
  41.             bit=x&1;
  42.             x>>=1;
  43.  
  44.             if(!(ptr->next[bit])) ptr->next[bit]=new trie();
  45.  
  46.             ptr=ptr->next[bit];
  47.             ptr->con++;
  48.         }
  49.         ptr->fin++;
  50.     }
  51.  
  52.     int check(int x)
  53.     {
  54.         trie *ptr=this;
  55.  
  56.         x=rev(x);bool bit;
  57.         for(int i=0;i<len;i++)
  58.         {
  59.             bit=x&1;
  60.             x>>=1;
  61.  
  62.             if(!(ptr->next[bit])) return 0;
  63.  
  64.             ptr=ptr->next[bit];
  65.         }
  66.         return ptr->fin;
  67.     }
  68.  
  69.     void delling(trie *ptr,const int &i,const int &x)
  70.     {
  71.         if(i==len)
  72.         {
  73.             ptr->fin--;
  74.             return;
  75.         }
  76.  
  77.         trie* nxt=ptr->next[x&1];
  78.         nxt->con--;
  79.  
  80.         delling(nxt,i+1,x>>1);
  81.  
  82.         if(nxt->con==0)
  83.         {
  84.             delete(nxt);
  85.             ptr->next[x&1]=0;
  86.         }
  87.  
  88.     }
  89.  
  90.     void del(const int &x)
  91.     {
  92.         if(!check(x)) return;
  93.         this->con--;
  94.         delling(this,0,rev(x));
  95.     }
  96.  
  97.     int kth(int k)
  98.     {
  99.         if(k>this->con)
  100.         {
  101.             cout<<"invalid\n";
  102.             return 0;
  103.         }
  104.         int rep=0;
  105.  
  106.         trie *ptr=this;
  107.         int cl,cr;
  108.  
  109.         bool bit;
  110.         #define child(x) ptr->next[(x)]
  111.         for(int i=0;i<len;i++)
  112.         {
  113.  
  114.             cl=(child(0))?child(0)->con:0;
  115.             cr=(child(1))?child(1)->con:0;
  116.  
  117.             bit=(cl<k);
  118.  
  119.             k-=bit?cl:0;
  120.  
  121.             rep=(rep<<1)|bit;
  122.  
  123.             ptr=ptr->next[bit];
  124.         }
  125.         return rep;
  126.     }
  127.  
  128.     int smallers(int x)
  129.     {
  130.         int rep=0;
  131.  
  132.         trie *ptr=this;
  133.  
  134.         x=rev(x);bool bit;
  135.         for(int i=0;i<len;i++)
  136.         {
  137.             bit=x&1;
  138.             x>>=1;
  139.  
  140.             rep+=(bit && ptr->next[0])?ptr->next[0]->con:0;
  141.  
  142.             if(!ptr->next[bit]) return rep;
  143.  
  144.             ptr=ptr->next[bit];
  145.         }
  146.  
  147.         return rep;
  148.     }
  149.  
  150. } *root = new trie();
  151.  
  152. int main()
  153. {
  154.     #ifdef dmdd
  155.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  156.     #endif // dmdd
  157.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  158.  
  159.     int q;
  160.     cin>>q;
  161.  
  162.     int x;char type;
  163.     for(int i=0;i<q;i++)
  164.     {
  165.         cin>>type>>x;
  166.         if(type=='I') root->add(x+oo);
  167.         else if(type=='D') root->del(x+oo);
  168.         else if(type=='K' && root->kth(x)) cout<<root->kth(x)-oo<<"\n";
  169.         else if(type=='C') cout<<root->smallers(x+oo)<<"\n";
  170.     }
  171.     return 0;
  172. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2
stdout
copy 
1
2
2
invalid
https://ideone.com/pnllun
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!