fork(1) download
copy 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <bitset>
  5. #include <string.h>
  6. #include <algorithm>
  7. #include <iomanip>
  8. #include <math.h>
  9. #include <time.h>
  10. #include <stdlib.h>
  11. #include <set>
  12. #include <map>
  13. #include <string>
  14. #include <queue>
  15. #include <cassert>
  16.  
  17. using namespace std;
  18.  
  19. const char infile[] = "input.in";
  20. const char outfile[] = "output.out";
  21.  
  22. ifstream fin(infile);
  23. ofstream fout(outfile);
  24.  
  25. const int MAXN = 100005;
  26. const int oo = 0x3f3f3f3f;
  27.  
  28. typedef vector<int> Graph[MAXN];
  29. typedef vector<int> :: iterator It;
  30.  
  31. const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
  32. const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
  33. const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
  34. const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }
  35.  
  36. struct Treap {
  37.     Treap *left, *right;
  38.     int key, subTree, priority;
  39.     Treap(Treap *_left, Treap *_right, int _key, int _priority, int _subTree = 1) {
  40.         left = _left;
  41.         right = _right;
  42.         key = _key;
  43.         priority = _priority;
  44.         subTree = _subTree;
  45.     }
  46. } *Root, *NIL;
  47.  
  48. inline void updateSubTree(Treap *& Node) {
  49.     if(Node == NIL) {
  50.         Node->subTree = 0;
  51.         return;
  52.     }
  53.     Node->subTree = 1 + Node->left->subTree + Node->right->subTree;
  54. }
  55.  
  56. inline void rotateLeft(Treap *& Node) {
  57.     Treap *aux = Node->left;
  58.     Node->left = aux->right;
  59.     aux->right = Node;
  60.  
  61.     Node = aux;
  62.  
  63.     updateSubTree(Node->right);
  64.     updateSubTree(Node);
  65. }
  66.  
  67. inline void rotateRight(Treap *& Node) {
  68.     Treap *aux = Node->right;
  69.     Node->right = aux->left;
  70.     aux->left = Node;
  71.  
  72.     Node = aux;
  73.  
  74.  
  75.     updateSubTree(Node->left);
  76.     updateSubTree(Node);
  77. }
  78.  
  79. inline void Balance(Treap *& Node) {
  80.     if(Node->left->priority > Node->priority)
  81.         rotateLeft(Node);
  82.     if(Node->right->priority > Node->priority)
  83.         rotateRight(Node);
  84. }
  85.  
  86. inline void Insert(Treap *& Node, int key, int pos, int priority) {
  87.     if(Node == NIL) {
  88.         Node = new Treap(NIL, NIL, key, priority, 1);
  89.         return;
  90.     }
  91.     if(pos <= Node->left->subTree + 1)
  92.         Insert(Node->left, key, pos, priority);
  93.     else Insert(Node->right, key, pos - Node->left->subTree - 1, priority);
  94.     Balance(Node);
  95.     updateSubTree(Node);
  96. }
  97.  
  98. inline void Erase(Treap *& Node, int pos) {
  99.     if(Node == NIL)
  100.         return;
  101.     if(Node->left->subTree + 1 == pos) {
  102.         if(Node->left == NIL && Node->right == NIL) {
  103.             delete Node;
  104.             Node = NIL;
  105.             return;
  106.         }
  107.         else {
  108.             if(Node->left->priority > Node->right->priority) {
  109.                 rotateLeft(Node);
  110.                 Erase(Node->right, pos - Node->left->subTree - 1);
  111.             }
  112.             else {
  113.                 rotateRight(Node);
  114.                 Erase(Node->left, pos);
  115.             }
  116.         }
  117.     }
  118.     else if(Node->left->subTree + 1 > pos)
  119.         Erase(Node->left, pos);
  120.     else Erase(Node->right, pos - Node->left->subTree - 1);
  121.  
  122.     updateSubTree(Node);
  123. }
  124.  
  125. inline int KthElement(Treap *& Node, int k) {
  126.     if(Node == NIL)
  127.         return 0;
  128.     if(Node->left->subTree + 1 == k)
  129.         return Node->key;
  130.     else
  131.         if(Node->left->subTree + 1 > k)
  132.             return KthElement(Node->left, k);
  133.         else
  134.             return KthElement(Node->right, k - Node->left->subTree - 1);
  135. }
  136.  
  137. inline void printTreap( Treap *& Node ) {
  138.     if(Node == NIL)
  139.         return;
  140.     printTreap(Node->left);
  141.     printTreap(Node->right);
  142. }
  143.  
  144. int main() {
  145.     cin.sync_with_stdio(false);
  146.     #ifndef ONLINE_JUDGE
  147.     freopen(infile, "r", stdin);
  148.     freopen(outfile, "w", stdout);
  149.     #endif
  150.  
  151.     srand(time(NULL));
  152.     NIL = new Treap(0, 0, 0, 0, 0);
  153.     Root = NIL;
  154.     NIL->left = NIL->right = NIL;
  155.  
  156.     int N, M;
  157.     scanf("%d%d", &N, &M);
  158.     for(int i = 1 ; i <= N ; ++ i)
  159.         Insert(Root, i, i, rand() + 1);
  160.     for(int t = 1 ; t <= M ; ++ t) {
  161.         char op; int x;
  162.         scanf(" %c %d", &op, &x);
  163.         if(op == 'D')    Erase(Root, x);
  164.         else   printf("%d\n", KthElement(Root, x));
  165.     }
  166.     fin.close();
  167.     fout.close();
  168.     return 0;
  169. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GKFzpd
language:
C++14 (gcc 8.3)
created:
10 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!