fork download
copy 
  1. /**
  2.     SPOJ: ORDERSET
  3.     initially array is empty. Then queries are:
  4.     I x: insert x
  5.     D x  delete x
  6.     C x: print the number of elements of S smaller than x 
  7.     K x: print the k'th element
  8. */
  9. #include<bits/stdc++.h>
  10. using namespace std;
  11.  
  12. typedef struct node
  13. {
  14.     int siz, key, prior;
  15.     struct node *l, *r;
  16.     node(){}
  17.     node(int key_):key(key_),siz(1),prior(rand()), l(NULL), r(NULL){}
  18. }node;
  19.  
  20. typedef node* pnode;
  21. int siz(pnode t)
  22. {
  23.     return t?t->siz:0;
  24. }
  25. void upd_siz(pnode &t)
  26. {
  27.     if(t) t->siz = 1 + siz(t->l) + siz(t->r);
  28. }
  29. void split(pnode t, pnode &l, pnode &r, int key)
  30. {
  31.     if(!t) l = r = NULL;
  32.     else if(key < t->key ) split(t->l, l, t->l, key), r = t;
  33.     else split(t->r, t->r, r, key), l=t;
  34.     upd_siz(t); 
  35. }
  36. void merg(pnode &t, pnode lf, pnode rg)
  37. {
  38.     if(!lf || !rg) t = lf?lf:rg;
  39.     else if(lf->prior > rg->prior) merg(lf->r, lf->r, rg), t = lf;
  40.     else merg(rg->l, lf, rg->l), t = rg;
  41.     upd_siz(t);
  42. }
  43. void eras(pnode &t, int key)
  44. {
  45.     if(!t) return;
  46.     if(t->key==key) {pnode tmp = t;merg(t, t->l, t->r);free(tmp);}
  47.     else eras(key<=t->key?t->l:t->r, key);
  48.     upd_siz(t);
  49. }
  50. void inseert(pnode &t, pnode nt)
  51. {
  52.     if(!t) t = nt;
  53.     else if(nt->prior > t->prior) split(t, nt->l, nt->r, nt->key), t = nt;
  54.     else inseert(nt->key <= t->key?t->l:t->r, nt);
  55.     upd_siz(t);
  56. }
  57. int cnt(pnode t, int key)
  58. {
  59.     pnode l, r;
  60.     split(t, l, r, key-1);
  61.     int ans = siz(l);
  62.     merg(t, l, r);
  63.     return ans;
  64. }
  65. int kth(pnode t, int k)
  66. {
  67.     int cntLeft = siz(t->l);
  68.     if(cntLeft==k-1)
  69.         return t->key;
  70.     else if(cntLeft>=k)
  71.         return kth(t->l, k);
  72.     else return kth(t->r, k - cntLeft - 1);
  73. }
  74. bool Find(pnode t, int x)
  75. {
  76.     if(!t) return 0;
  77.     if(t->key == x)
  78.         return 1;
  79.     if(x <= t->key)
  80.         return Find(t->l, x);
  81.     return Find(t->r, x);
  82. }
  83.  
  84. int main()
  85. {
  86.     //freopen("in.txt", "r", stdin);
  87.     //freopen("out.txt", "w", stdout);
  88.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  89.     int n, x;
  90.     cin>>n;
  91.     pnode t = NULL;
  92.     while(n--)
  93.     {
  94.         string op;
  95.         cin>>op>>x;
  96.         if(op[0]=='I' && !Find(t, x))
  97.         {
  98.             inseert(t, new node(x));
  99.             //print(t);
  100.         }
  101.         else if(op[0]=='D' && Find(t, x))
  102.         {
  103.             eras(t, x);
  104.         }
  105.         else if(op[0]=='C')
  106.         {
  107.             cout << cnt(t, x) << "\n";
  108.         }
  109.         else if(op[0]=='K')
  110.         {
  111.             if(x>siz(t))
  112.                 cout << "invalid\n";
  113.             else cout << kth(t, x) << "\n";
  114.         }
  115.     }
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N7XOC5
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!