fork download
copy 
  1. /// treap by muoii
  2.  
  3. /// vn.spoj.com/problems/ORDERSET/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 1007
  9. #define oo 1000000007
  10. #define mid ((l+r)>>1)
  11. #define meset(a,x) memset(a,x,sizeof(a))
  12. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  13. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  14.  
  15. class treap{
  16.  
  17.     typedef struct item{
  18.         int val,prior,siz,cnt;
  19.         item *l,*r;
  20.  
  21.         item(const int &v): val(v), prior(rand()<<rand()%16 | rand()), siz(1), cnt(1), l(0), r(0) {};
  22.  
  23.  
  24.         static int size(item* ptr) { return ptr?ptr->siz:0; }
  25.  
  26.         void resize() { siz=size(l)+size(r)+1; }
  27.     } *pitem;
  28.  
  29.     static int size(pitem ptr) { return ptr?ptr->siz:0; }
  30.  
  31.     void split(pitem node,const int &val,pitem &l,pitem &r)
  32.     {
  33.         if(!node) l=r=0;
  34.         else if(node->val < val)
  35.             split(node->r,val,node->r,r),node->resize(),l=node;
  36.         else split(node->l,val,l,node->l),node->resize(),r=node;
  37.     }
  38.  
  39.     pitem merge(const pitem &l,const pitem &r)
  40.     {
  41.         if(!l || !r) return l?l:r;
  42.  
  43.         if(l->prior < r->prior)
  44.         {
  45.             l->r=merge(l->r,r);
  46.             l->resize();
  47.             return l;
  48.         }
  49.         else
  50.         {
  51.             r->l=merge(l,r->l);
  52.             r->resize();
  53.             return r;
  54.         }
  55.     }
  56.  
  57.     pitem root=0;
  58.  
  59. public:
  60.  
  61.     int size() { return size(root); };
  62.  
  63.     pitem find(const pitem &node,const int &val)
  64.     {
  65.         if(!node || node->val==val) return node;
  66.  
  67.         return (node->val > val)?find(node->l,val):find(node->r,val);
  68.     }
  69.  
  70.     pitem find(const int &val)
  71.     {
  72.         return find(root,val);
  73.     }
  74.  
  75.     void insert(const int &val)
  76.     {
  77.         pitem l,m,r;
  78.  
  79.         l=m=r=0;
  80.  
  81.         split(root,val,l,r);
  82.         split(r,val+1,m,r);
  83.  
  84.         m=m?m:new item(val);
  85.  
  86.         root=merge(l,merge(m,r));
  87.     }
  88.  
  89.     void erase(const int &val)
  90.     {
  91.         pitem l,m,r;
  92.  
  93.         l=m=r=0;
  94.  
  95.         split(root,val,l,r);
  96.         split(r,val+1,m,r);
  97.  
  98.         delete m;
  99.  
  100.         root=merge(l,r);
  101.     }
  102.  
  103.     int kth(const pitem &node,const int &k)
  104.     {
  105.         if(size(node->l)+1 == k) return node->val;
  106.  
  107.         return (size(node->l)>=k)?kth(node->l,k):kth(node->r,k-size(node->l)-1);
  108.     }
  109.  
  110.     void printf_kth(const int &k)
  111.     {
  112.         if(k>size(root))cout<<"invalid\n";
  113.         else cout<<kth(root,k)<<"\n";
  114.     }
  115.  
  116.     int smaller(const int &val)
  117.     {
  118.         pitem l,r;
  119.  
  120.         split(root,val,l,r);
  121.  
  122.         int rep=size(l);
  123.  
  124.         merge(l,r);
  125.  
  126.         return rep;
  127.     }
  128. };
  129.  
  130. int main()
  131. {
  132.     #ifdef dmdd
  133.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  134.     #endif // dmdd
  135.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  136.  
  137.     int q,x;
  138.  
  139.     char query;
  140.  
  141.     cin>>q;
  142.  
  143.     treap tree;
  144.  
  145.     for(int i=0;cin>>query>>x,i<q;i++)
  146.         if(query=='I') tree.insert(x);
  147.         else if(query=='D') tree.erase(x);
  148.         else if(query=='K') tree.printf_kth(x);
  149.         else cout<<tree.smaller(x)<<"\n";
  150.  
  151.     return 0;
  152. }
Success #stdin #stdout 0s 4460KB
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/kQqT7n
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!