fork download
copy 
  1. /* -------------------------------- */
  2. /* Name: MD. Khairul Basar          */
  3. /* Institute: HSTU                  */
  4. /* Dept: CSE                        */
  5. /* Email: khairul.basar93@gmail.com */
  6. /* -------------------------------- */
  7.  
  8. /// Updated by CodingKnight at Codeforces on Sept 23, 2018
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13.  
  14. class AVL_tree
  15. {
  16. public:
  17.     int size;
  18. private:
  19.     int key, height; AVL_tree *left, *right;
  20.  
  21.     friend int get_height( AVL_tree* t )
  22.     {
  23.         return t ? t->height : 0;
  24.     }
  25.  
  26.     friend int get_balance( AVL_tree* t )
  27.     {
  28.         return t ? ( get_height(t->left) - get_height(t->right) ) : 0;
  29.     }
  30.  
  31.     friend int get_size( AVL_tree* t )
  32.     {
  33.         return t ? t->size : 0;
  34.     }
  35.  
  36.     AVL_tree* update()
  37.     {
  38.         return  height = max( get_height(left), get_height(right) ) + 1,
  39.                 size = get_size(left) + get_size(right) + 1, this;
  40.     }
  41.  
  42.     AVL_tree* left_rotate()
  43.     {
  44.         AVL_tree *y = right, *t = y->left; return y->left = this, right = t, update(), y->update();
  45.     }
  46.  
  47.     AVL_tree* right_rotate()
  48.     {
  49.         AVL_tree *y = left, *t = y->right; return y->right = this, left = t, update(), y->update();
  50.     }
  51.  
  52.     AVL_tree* find_min()
  53.     {
  54.         AVL_tree *t = this;
  55.  
  56.         while( t->left != nullptr )
  57.             t = t->left;
  58.  
  59.         return t;
  60.     }
  61.  
  62.     AVL_tree* balance()
  63.     {
  64.         int balance = get_balance( this );
  65.  
  66.         if( balance >  1 and get_balance( left ) >= 0 )
  67.             return right_rotate();
  68.  
  69.         if( balance < -1 and get_balance( right ) <= 0 )
  70.             return left_rotate();
  71.  
  72.         if( balance >  1 and get_balance( left  ) <  0 )
  73.             return left = left->left_rotate(), right_rotate();
  74.  
  75.         if( balance < -1 and get_balance( right ) >  0 )
  76.             return right = right->right_rotate(), left_rotate();
  77.  
  78.         return this;
  79.     }
  80.  
  81.     AVL_tree* insert( int k )
  82.     {
  83.         if( k < key )
  84.             left = insert_key( left, k );
  85.         else if( k > key )
  86.             right = insert_key( right, k );
  87.         else
  88.             return this;
  89.  
  90.         int balance = get_balance( update() );
  91.  
  92.         if( balance >  1 and k < left->key )
  93.             return right_rotate();
  94.  
  95.         if( balance < -1 and k > right->key )
  96.             return left_rotate();
  97.  
  98.         if( balance >  1 and k > left->key )
  99.             return left = left->left_rotate(), right_rotate();
  100.  
  101.         if( balance < -1 and k < right->key )
  102.             return right = right->right_rotate(), left_rotate();
  103.  
  104.         return this;
  105.     }
  106.  
  107.     AVL_tree* Delete( int k )
  108.     {
  109.         if( k < key )
  110.             left = delete_key( left, k );
  111.         else if( k > key )
  112.             right = delete_key( right, k );
  113.         else
  114.         {
  115.             AVL_tree *t = nullptr;
  116.  
  117.             if( left == nullptr or right == nullptr )
  118.             {
  119.                 if( left != nullptr )
  120.                     t = left;
  121.                 else
  122.                     t = right;
  123.  
  124.                 if( t == nullptr )
  125.                     t = this, key = INT_MIN;
  126.                 else
  127.                     *this = *t;
  128.  
  129.                 if ( t != this )
  130.                     delete t;
  131.             }
  132.             else
  133.                 t = right->find_min(), key = t->key, right = delete_key( right, key );
  134.         }
  135.  
  136.         return this;
  137.     }
  138.  
  139. public:
  140.     AVL_tree( int k ) : size( 1 ), key( k ), height( 1 ), left( nullptr ), right( nullptr ) {}
  141.  
  142.     friend AVL_tree* insert_key( AVL_tree* t, int k )
  143.     {
  144.         return t ? t->insert( k ) : new AVL_tree( k );
  145.     }
  146.  
  147.     friend AVL_tree* delete_key( AVL_tree* t, int k )
  148.     {
  149.         if ( t != nullptr )
  150.             t = t->Delete( k );
  151.  
  152.         if ( t == nullptr )
  153.             return nullptr;
  154.  
  155.         if ( t->key != INT_MIN )
  156.             return t->update()->balance();
  157.  
  158.         delete t; return nullptr;
  159.     }
  160.  
  161.     int find_k_smallest( int k )
  162.     {
  163.         int left_size = get_size( left ), l = left_size + 1;
  164.  
  165.         if( k == l )
  166.             return key;
  167.  
  168.         if( left_size < k )
  169.             return right->find_k_smallest( k - l );
  170.  
  171.         return left->find_k_smallest( k );
  172.     }
  173.  
  174.     int count_smaller( int k )
  175.     {
  176.         int total = 0;
  177.  
  178.         if( k  < key )
  179.         {
  180.             if ( left )
  181.                 total = left->count_smaller( k );
  182.         }
  183.         else if( k > key )
  184.         {
  185.             total = get_size( left ) + 1;
  186.  
  187.             if ( right )
  188.                 total += right->count_smaller( k );
  189.         }
  190.         else
  191.             total = get_size( left );
  192.  
  193.         return total;
  194.     }
  195. };
  196.  
  197. int main()
  198. {
  199.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  200.  
  201.     int q, a; char c; AVL_tree *root = nullptr;
  202.  
  203.     for( cin >> q; q > 0; q-- )
  204.         switch( ( cin >> c >> a, c ) )
  205.         {
  206.         case 'I':
  207.             root = insert_key( root, a ); break;
  208.         case 'D':
  209.             root = delete_key( root, a ); break;
  210.         case 'K':
  211.             if( root == nullptr or a > root->size )
  212.                 cout << "invalid" << '\n';
  213.             else
  214.                 cout << root->find_k_smallest( a ) << '\n';
  215.             break;
  216.         case 'C':
  217.             if ( root == nullptr )
  218.                 cout << '0' << '\n';
  219.             else
  220.                 cout << root->count_smaller( a ) << '\n';
  221.         }
  222. }
Success #stdin #stdout 0s 15248KB
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/7q3BID
Order statistic set
language:
C++14 (gcc 8.3)
created:
5 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!