Advertisement
Misbah_Uddin_Tareq

Order statstic set - pdbs

Jul 14th, 2020
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. /**==============================================================*
  2. *            "Bismillahir Rahmanir Raheem"                       *
  3. *        Author          :  Misbah Uddin Tareq.                  *
  4. *        Semester        :  5(C),CSE                             *
  5. *        University      :  Leading University,Sylhet.           *
  6. *===============================================================**/
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10. #define  ll                     long long
  11. #define  pb                     push_back
  12. #define  pii                    pair<int,int>
  13. #define  pll                    pair<ll,ll>
  14. #define  ff                     first
  15. #define  ss                     second
  16. #define  mxx                    100005
  17. #define  endl                   "\n"
  18. #define  mod                    1e9+7
  19. #define  pi                     acos(-1.0)
  20. #define  PQ                     priority_queue
  21. #define  mem(a,b)               memset(a, b, sizeof(a))
  22. #define  bug(a)                 cout<<#a<<":"<<a<<endl
  23. #define  all(x)                 (x).begin(),(x).end()
  24. #define  allr(x)                (x).rbegin(),(x).rend()
  25. #define  double_print(x,a)      cout<<fixed<<setprecision(x)<<a<<endl
  26.  
  27.  
  28. #include <ext/pb_ds/tree_policy.hpp>
  29. #include <ext/pb_ds/assoc_container.hpp>
  30. using namespace __gnu_pbds;
  31. template <typename T>  using orderedSet =
  32.     tree<T, null_type, less<T>,
  33.     rb_tree_tag, tree_order_statistics_node_update>;
  34.  
  35. int main()
  36. {
  37.     ios::sync_with_stdio(0);
  38.     //cin.tie(0);
  39.  
  40.     orderedSet<ll>st;
  41.     ll q;
  42.     cin>>q;
  43.     while(q--)
  44.     {
  45.         char c;
  46.         cin>>c;
  47.         ll x;
  48.         cin>>x;
  49.  
  50.         if(c=='I')
  51.             st.insert(x);
  52.         else if(c=='C')
  53.             cout<<st.order_of_key(x)<<endl;
  54.         else if(c=='K')
  55.         {
  56.             x--;
  57.             if(x>=st.size())
  58.                 cout<<"invalid\n";
  59.             else
  60.             {
  61.                 ll p=*st.find_by_order(x);
  62.                 cout<<p<<endl;
  63.             }
  64.         }
  65.         else if(c=='D')
  66.         {
  67.             if(st.size()>0)
  68.             {
  69.                 auto p=st.lower_bound(x);
  70.                 if(*p==x)
  71.                     st.erase(p);
  72.             }
  73.         }
  74.     }
  75.  
  76.     return 0;
  77. }
  78.  
  79. https://www.spoj.com/problems/ORDERSET/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement