fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. template <class T>
  7. struct treap {
  8.     private:
  9.         struct xor_128 {
  10.             unsigned long long x,y,z,w;
  11.             xor_128(): x(198535678165727856), y(2378257282762967), z(51738523678237522), w(75175185715718) {}
  12.             unsigned long long next() {
  13.                 unsigned long long t=x^(x<<11);
  14.                 x=y;y=z;z=w;
  15.                 return w=w^(w>>19)^t^(t>>8);
  16.             }
  17.         };
  18.  
  19.         struct node {
  20.             T key;
  21.             node *left, *right;
  22.             unsigned long long priority;
  23.             unsigned size;
  24.         };
  25.  
  26.         typedef node *node_ptr;
  27.  
  28.         xor_128 rng;
  29.         node_ptr root;
  30.  
  31.         unsigned long long next() {
  32.             return rng.next();
  33.         }
  34.  
  35.         unsigned size(node_ptr a) {
  36.             if(a==NULL) return 0;
  37.             else return a->size;
  38.         }
  39.  
  40.         unsigned update_size(node_ptr &a) {
  41.             if(a!=NULL) a->size=1+size(a->left)+size(a->right);
  42.         }
  43.  
  44.         node_ptr new_node(T key) {
  45.             node_ptr res=(node_ptr)malloc(sizeof(node));
  46.             res->key=key;
  47.             res->left=NULL;
  48.             res->right=NULL;
  49.             res->priority=next();
  50.             res->size=1;
  51.             return res;
  52.         }
  53.  
  54.         node_ptr right_rotation(node_ptr y) {
  55.             node_ptr x=y->left;
  56.             node_ptr t2=x->right;
  57.             y->left=t2;
  58.             x->right=y;
  59.             update_size(y);
  60.             update_size(x);
  61.             return x;
  62.         }
  63.  
  64.         node_ptr left_rotation(node_ptr x) {
  65.             node_ptr y=x->right;
  66.             node_ptr t2=y->left;
  67.             x->right=t2;
  68.             y->left=x;
  69.             update_size(x);
  70.             update_size(y);
  71.             return y;
  72.         }
  73.  
  74.         bool find(node_ptr root, T key) {
  75.             if(root==NULL) return false;
  76.             if(key==root->key) return true;
  77.             else if(key<root->key) return find(root->left,key);
  78.             else return find(root->right,key);
  79.         }
  80.  
  81.         node_ptr remove_it(node_ptr root) {
  82.             assert(root!=NULL);
  83.             if(root->left==NULL && root->right==NULL) return NULL;
  84.             else if(root->left==NULL) {
  85.                 root=left_rotation(root);
  86.                 root->left=remove_it(root->left);
  87.             }
  88.             else if(root->right==NULL) {
  89.                 root=right_rotation(root);
  90.                 root->right=remove_it(root->right);
  91.             }
  92.             else {
  93.                 if(root->left->priority>root->right->priority) {
  94.                     root=right_rotation(root);
  95.                     root->right=remove_it(root->right);
  96.                 }
  97.                 else {
  98.                     root=left_rotation(root);
  99.                     root->left=remove_it(root->left);
  100.                 }
  101.             }
  102.             update_size(root);
  103.             return root;
  104.         }
  105.  
  106.         node_ptr insert(node_ptr root, T key) {
  107.             if(root==NULL) return new_node(key);
  108.             else if(key<root->key) {
  109.                 root->left=insert(root->left,key);
  110.                 if(root->left->priority<root->priority) root=right_rotation(root);
  111.             }
  112.             else {
  113.                 root->right=insert(root->right,key);
  114.                 if(root->right->priority<root->priority) root=left_rotation(root);
  115.             }
  116.             update_size(root);
  117.             return root;
  118.         }
  119.  
  120.         node_ptr erase(node_ptr root, T key) {
  121.             if(root==NULL) return root;
  122.             else if(root->key==key) {
  123.                 root=remove_it(root);
  124.             }
  125.             else if(key<root->key) root->left=erase(root->left,key);
  126.             else root->right=erase(root->right,key);
  127.             update_size(root);
  128.             return root;
  129.         }
  130.  
  131.         T kth(node_ptr root, unsigned k) {
  132.             if(size(root->left)+1==k) return root->key;
  133.             else if(size(root->left)>=k) return kth(root->left,k);
  134.             else return kth(root->right,k-1-size(root->left));
  135.         }
  136.  
  137.         unsigned count_less(node_ptr root, T k) {
  138.             if(root==NULL) return 0;
  139.             if(root->key==k) return size(root->left);
  140.             else if(k<root->key) return count_less(root->left,k);
  141.             else return 1+size(root->left)+count_less(root->right,k);
  142.         }
  143.  
  144.         void inorder(node_ptr root) {
  145.             if(root==NULL) return;
  146.             inorder(root->left);
  147.             cout<<"( "<<root->key<<" , "<<root->size<<" )"<<' ';
  148.             inorder(root->right);
  149.         }
  150.  
  151.     public:
  152.         treap(): root(NULL) {}
  153.  
  154.         unsigned size() {
  155.             return size(root);
  156.         }
  157.  
  158.         bool find(T key) {
  159.             return find(root,key);
  160.         }
  161.  
  162.         void insert(T key) {
  163.             root=insert(root,key);
  164.         }
  165.  
  166.         void erase(T key) {
  167.             root=erase(root,key);
  168.         }
  169.  
  170.         T kth(unsigned k) {
  171.             return kth(root,k);
  172.         }
  173.  
  174.         unsigned count_less(T k) {
  175.             return count_less(root,k);
  176.         }
  177.  
  178.         void inorder() {
  179.             inorder(root);
  180.         }
  181.  
  182.         void clear() {
  183.             root=NULL;
  184.         }
  185. };
  186.  
  187. int tests,current_case;
  188. int n,q;
  189. treap < int > t;
  190.  
  191. void message(int current_case) {
  192.     //cerr<<"Case "<<current_case<<" solved!"<<endl;
  193.     //fprintf(stderr, "Case %d solved!\n", current_case);
  194. }
  195.  
  196. int get_kth(int k) {
  197.     int left=0,right=n,middle;
  198.     while(right-left>1) {
  199.         middle=(left+right)>>1;
  200.         if(middle-t.count_less(middle+1)>=k) right=middle;
  201.         else left=middle;
  202.     }
  203.     return right;
  204. }
  205.  
  206. int main() {
  207.     //ios_base::sync_with_stdio(false);
  208.     //cin.tie(NULL);
  209.     int i,x;
  210.     char type[4];
  211.  
  212.     tests=1;
  213.     //scanf("%d", &tests);
  214.     //cin>>tests;
  215.     for(current_case=1;current_case<=tests;current_case++) {
  216.         scanf("%d %d", &n, &q);
  217.         t.clear();
  218.         while(q--) {
  219.             scanf("%s", type);
  220.             if(type[0]=='D') {
  221.                 scanf("%d", &x);
  222.                 x=get_kth(x);
  223.                 t.insert(x);
  224.             }
  225.             else {
  226.                 scanf("%d", &x);
  227.                 printf("%d\n", get_kth(x));
  228.             }
  229.         }
  230.  
  231. 		MESSAGE:
  232.         message(current_case);
  233.     }
  234.  
  235.     return 0;
  236. }
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7tULry
language:
C++14 (gcc 8.3)
created:
7 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!