fork download
copy 
  1. /* -------------------------------- */
  2. /* Name: MD. Khairul Basar          */
  3. /* Institute: HSTU                  */
  4. /* Dept: CSE                        */
  5. /* Email: khairul.basar93@gmail.com */
  6. /* -------------------------------- */
  7.  
  8. #include <bits/stdc++.h>
  9. /* all header files */
  10.  
  11. #define fs            first
  12. #define sc            second
  13. #define sp            printf(" ")
  14. #define nl            printf("\n")
  15. #define pb(a)         push_back(a)
  16.  
  17. #define setzero(a)    memset(a,0,sizeof(a))
  18. #define setneg(a)     memset(a,-1,sizeof(a))
  19. #define setinf(a)     memset(a,126,sizeof(a))
  20.  
  21. #define tc1(x)        printf("Case %d: ",x)
  22. #define tc2(x)        printf("Case #%d: ",x)
  23. #define tc3(x)        printf("Case %d:\n",x)
  24. #define tc4(x)        printf("Case #%d:\n",x)
  25.  
  26. #define iin(x)        scanf("%d",&x)
  27. #define din(x)        scanf("%lf",&x)
  28. #define lin(x)        scanf("%lld",&x)
  29. #define clin(x)       scanf("%I64d",&x)
  30.  
  31. #define pr1(x)        cout<<x<<"\n"
  32. #define pr2(x,y)      cout<<x<<" "<<y<<"\n"
  33. #define pr3(x,y,z)    cout<<x<<" "<<y<<" "<<z<<"\n"
  34. #define pr4(w,x,y,z)  cout<<w<<" "<<x<<" "<<y<<" "<<z<<"\n"
  35. #define fast          ios::sync_with_stdio(0)
  36. #define read          freopen("input.txt","r",stdin)
  37. #define write         freopen("output.txt","w",stdout)
  38. #define prflag1(flag) printf("%s\n",(flag)?"YES":"NO")
  39. #define prflag2(flag) printf("%s\n",(flag)?"Yes":"No")
  40. #define prflag3(flag) printf("%s\n",(flag)?"yes":"no")
  41. /* macro definitions */
  42.  
  43. using namespace std;
  44.  
  45. typedef long long LL;
  46. typedef unsigned long long ULL;
  47. typedef pair<int, int>pii;
  48. typedef pair<LL, LL>pll;
  49. typedef vector<int>vi;
  50. typedef vector<LL>vll;
  51. typedef vector<pii>vpii;
  52. typedef vector<pll>vpll;
  53. /* type definitions */
  54.  
  55. LL MOD_EXPO(LL b, LL p, LL m)
  56. {
  57.     if(p==0)
  58.         return 1;
  59.     LL ret=MOD_EXPO(b,p/2,m)%m;
  60.     ret=(ret*ret)%m;
  61.     return ((p&1) ? (ret*b)%m : ret%m);
  62. }
  63. LL POWER(LL N, LL K)
  64. {
  65.     LL i,ans=1;
  66.     for(i=1; i<=K; i++)
  67.         ans*=N;
  68.     return ans;
  69. }
  70. int SET(int N, int pos)
  71. {
  72.     return (N | (1<<pos));
  73. }
  74. int RESET(int N, int pos)
  75. {
  76.     return (N & !(1<<pos));
  77. }
  78. bool CHECK(int N, int pos)
  79. {
  80.     return (N & (1<<pos));
  81. }
  82. /* necessary functions */
  83.  
  84. int dx4[]= {1,-1,0,0};
  85. int dy4[]= {0,0,1,-1};
  86. int dx6[]= {0,0,1,-1,0,0};
  87. int dy6[]= {1,-1,0,0,0,0};
  88. int dz6[]= {0,0,0,0,1,-1};
  89. int dx8[]= {1,-1,0,0,-1,1,-1,1};
  90. int dy8[]= {0,0,1,-1,1,1,-1,-1};
  91. int dkx8[]= {-1,1,-1,1,-2,-2,2,2};
  92. int dky8[]= {2,2,-2,-2,1,-1,1,-1};
  93. /* direction arrays */
  94.  
  95. int tc=1;
  96. const double eps=1e-9;
  97. const double pi=acos(-1.0);
  98. const long long int mx=1e5;
  99. const long long int mod=1e9+7;
  100. /* global declarations */
  101.  
  102. struct node
  103. {
  104.     int key;
  105.     int height;
  106.     node *left;
  107.     node *right;
  108.     int subtree_size;
  109. };
  110.  
  111. node* create_node(int key_)
  112. {
  113.     node *child = new node;
  114.  
  115.     child->key = key_;
  116.     child->height = 1;
  117.     child->left = NULL;
  118.     child->right = NULL;
  119.     child->subtree_size = 1;
  120.  
  121.     return child;
  122. }
  123.  
  124. int get_height(node *current_node)
  125. {
  126.     if(current_node == NULL)
  127.         return 0;
  128.     return current_node->height;
  129. }
  130.  
  131. int get_balance(node *current_node)
  132. {
  133.     if(current_node == NULL)
  134.         return 0;
  135.     return get_height(current_node->left) - get_height(current_node->right);
  136. }
  137.  
  138. int get_subtree_size(node *current_node)
  139. {
  140.     if(current_node == NULL)
  141.         return 0;
  142.     return current_node->subtree_size;
  143. }
  144.  
  145. node* left_rotate(node *x)
  146. {
  147.     node *y = x->right;
  148.     node *t2 = y->left;
  149.  
  150.     y->left = x;
  151.     x->right = t2;
  152.  
  153.     x->height = max(get_height(x->left), get_height(x->right)) + 1;
  154.     y->height = max(get_height(y->left), get_height(y->right)) + 1;
  155.  
  156.     x->subtree_size = get_subtree_size(x->left) + get_subtree_size(x->right) + 1;
  157.     y->subtree_size = get_subtree_size(y->left) + get_subtree_size(y->right) + 1;
  158.  
  159.     return y;
  160. }
  161.  
  162. node* right_rotate(node *x)
  163. {
  164.     node *y = x->left;
  165.     node *t2 = y->right;
  166.  
  167.     y->right = x;
  168.     x->left = t2;
  169.  
  170.     x->height = max(get_height(x->left), get_height(x->right)) + 1;
  171.     y->height = max(get_height(y->left), get_height(y->right)) + 1;
  172.  
  173.     x->subtree_size = get_subtree_size(x->left) + get_subtree_size(x->right) + 1;
  174.     y->subtree_size = get_subtree_size(y->left) + get_subtree_size(y->right) + 1;
  175.  
  176.     return y;
  177. }
  178.  
  179. node* left_left_case(node *current_node)
  180. {
  181.     return right_rotate(current_node);
  182. }
  183.  
  184. node* right_right_case(node *current_node)
  185. {
  186.     return left_rotate(current_node);
  187. }
  188.  
  189. node* left_right_case(node *current_node)
  190. {
  191.     current_node->left = left_rotate(current_node->left);
  192.     return right_rotate(current_node);
  193. }
  194.  
  195. node* right_left_case(node *current_node)
  196. {
  197.     current_node->right = right_rotate(current_node->right);
  198.     return left_rotate(current_node);
  199. }
  200.  
  201. node* find_min(node *current_node)
  202. {
  203.     while(current_node->left != NULL)
  204.         current_node = current_node->left;
  205.  
  206.     return current_node;
  207. }
  208.  
  209. node* insert_node(node *current_node, int key_)
  210. {
  211.     if(current_node == NULL)
  212.         return create_node(key_);
  213.  
  214.     if(key_ < current_node->key)
  215.         current_node->left = insert_node(current_node->left, key_);
  216.     else if(key_ > current_node->key)
  217.         current_node->right = insert_node(current_node->right, key_);
  218.     else
  219.         return current_node;
  220.  
  221.     current_node->height = max(get_height(current_node->left), get_height(current_node->right)) + 1;
  222.     current_node->subtree_size = get_subtree_size(current_node->left) + get_subtree_size(current_node->right) + 1;
  223.  
  224.     int balance = get_balance(current_node);
  225.  
  226.     if(balance > 1 && key_ < current_node->left->key)
  227.         return left_left_case(current_node);
  228.  
  229.     if(balance < -1 && key_ > current_node->right->key)
  230.         return right_right_case(current_node);
  231.  
  232.     if(balance > 1 && key_ > current_node->left->key)
  233.         return left_right_case(current_node);
  234.  
  235.     if(balance < -1 && key_ < current_node->right->key)
  236.         return right_left_case(current_node);
  237.  
  238.     return current_node;
  239. }
  240.  
  241. node* delete_node(node *current_node, int key_)
  242. {
  243.     if(current_node == NULL)
  244.         return current_node;
  245.  
  246.     if(key_ < current_node->key)
  247.         current_node->left = delete_node(current_node->left, key_);
  248.     else if(key_ > current_node->key)
  249.         current_node->right = delete_node(current_node->right, key_);
  250.     else
  251.     {
  252.         if(current_node->left == NULL || current_node->right == NULL)
  253.         {
  254.             node *temp = NULL;
  255.  
  256.             if(current_node->left != NULL)
  257.                 temp = current_node->left;
  258.             else
  259.                 temp = current_node->right;
  260.  
  261.             if(temp == NULL)
  262.             {
  263.                 temp = current_node;
  264.                 current_node = NULL;
  265.             }
  266.             else
  267.             {
  268.                 current_node->key = temp->key;
  269.                 current_node->left = temp->left;
  270.                 current_node->right = temp->right;
  271.                 current_node->height = temp->height;
  272.                 current_node->subtree_size = temp->subtree_size;
  273.             }
  274.  
  275.             delete temp;
  276.         }
  277.         else
  278.         {
  279.             node *temp = find_min(current_node->right);
  280.  
  281.             current_node->key = temp->key;
  282.             current_node->right = delete_node(current_node->right, temp->key);
  283.         }
  284.     }
  285.  
  286.     if(current_node == NULL)
  287.         return current_node;
  288.  
  289.     current_node->height = max(get_height(current_node->left), get_height(current_node->right)) + 1;
  290.     current_node->subtree_size = get_subtree_size(current_node->left) + get_subtree_size(current_node->right) + 1;
  291.  
  292.     int balance = get_balance(current_node);
  293.  
  294.     if(balance > 1 && get_balance(current_node->left) >= 0)
  295.         return left_left_case(current_node);
  296.  
  297.     if(balance < -1 && get_balance(current_node->right) <= 0)
  298.         return right_right_case(current_node);
  299.  
  300.     if(balance > 1 && get_balance(current_node->left) < 0)
  301.         return left_right_case(current_node);
  302.  
  303.     if(balance < -1 && get_balance(current_node->right) > 0)
  304.         return right_left_case(current_node);
  305.  
  306.     return current_node;
  307. }
  308.  
  309. int count_smaller(node *current_node, int key_)
  310. {
  311.     if(current_node == NULL)
  312.         return 0;
  313.  
  314.     int total = 0;
  315.  
  316.     if(key_ < current_node->key)
  317.     {
  318.         total = count_smaller(current_node->left, key_);
  319.     }
  320.     else if(key_ > current_node->key)
  321.     {
  322.         total = get_subtree_size(current_node->left) + 1;
  323.         total = total + count_smaller(current_node->right, key_);
  324.     }
  325.     else
  326.     {
  327.         total = get_subtree_size(current_node->left);
  328.     }
  329.  
  330.     return total;
  331. }
  332.  
  333. int find_k_smallest(node *current_node, int k)
  334. {
  335.     int ret = INT_MIN;
  336.  
  337.     while(current_node != NULL)
  338.     {
  339.         int left_subtree_size = get_subtree_size(current_node->left);
  340.  
  341.         if(left_subtree_size + 1 == k)
  342.         {
  343.             ret = current_node->key;
  344.             break;
  345.         }
  346.         else if(left_subtree_size < k)
  347.         {
  348.             k -= left_subtree_size + 1;
  349.             current_node = current_node->right;
  350.         }
  351.         else
  352.         {
  353.             current_node = current_node->left;
  354.         }
  355.     }
  356.  
  357.     return ret;
  358. }
  359.  
  360. void delete_tree(node *current_node)
  361. {
  362.     if(current_node == NULL)
  363.     {
  364.         delete current_node;
  365.         return;
  366.     }
  367.     delete_tree(current_node->left);
  368.     delete_tree(current_node->right);
  369.     return;
  370. }
  371.  
  372. int main()
  373. {
  374.     int q,a;
  375.     char ch[5];
  376.     node *root = NULL;
  377.  
  378.     cin>>q;
  379.     while(q--)
  380.     {
  381.         scanf("%s %d",ch,&a);
  382.  
  383.         if(ch[0] == 'I')
  384.         {
  385.             root = insert_node(root, a);
  386.         }
  387.         else if(ch[0] == 'D')
  388.         {
  389.             root = delete_node(root, a);
  390.         }
  391.         else if(ch[0] == 'K')
  392.         {
  393.             if(a > root->subtree_size)
  394.             {
  395.                 printf("invalid\n");
  396.             }
  397.             else
  398.             {
  399.                 a = find_k_smallest(root, a);
  400.                 printf("%d\n",a);
  401.             }
  402.         }
  403.         else if(ch[0] == 'C')
  404.         {
  405.             a = count_smaller(root, a);
  406.             printf("%d\n",a);
  407.         }
  408.     }
  409.  
  410.     delete_tree(root);
  411.     return 0;
  412. }
  413.  
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/l7a0jg
language:
C++ 4.3.2 (gcc-4.3.2)
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!