fork download
copy 
  1. # include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pii pair<int, int>
  6. #define pll pair<ll, ll>
  7.  
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define mp make_pair
  11.  
  12. #define fi first
  13. #define se second
  14.  
  15. typedef long long ll;
  16. typedef long double ld;
  17. typedef unsigned long long ull;
  18.  
  19.  
  20. const int inf = (int)1e9 + 7;
  21. const int maxn = (int)6e5 + 7;
  22. const int lmaxn = (int)2e6 + 7;
  23. const ll linf = (ll)1e16 + 7;
  24.  
  25. const ld eps = ld(1e-11);
  26.  
  27. const ll dx[] = {-1, 0, 0, 1};
  28. const ll dy[] = {0, -1, 1, 0};
  29.  
  30. struct node{
  31.     node *l, *r;
  32.     ll val;
  33.     node(){
  34.         l = r = nullptr;
  35.         val = 0;
  36.     }
  37.     ~node(){}
  38. };
  39.  
  40. struct tree{
  41.     node *root;
  42.     tree(){
  43.         root = new node();
  44.     }
  45.     void upd(node *&v, ll tl, ll tr, ll pos, ll val){
  46.         if(tl == tr){
  47.             v -> val = val;
  48.             return;
  49.         }
  50.         ll tm = (tl + tr) >> 1ll;
  51.         if(v -> l == nullptr) v -> l = new node();
  52.         if(v -> r == nullptr) v -> r = new node();
  53.         if(pos <= tm)
  54.             upd(v -> l, tl, tm, pos, val);
  55.         else
  56.             upd(v -> r, tm + 1, tr, pos, val);
  57.         v -> val = (v -> l) -> val + (v -> r) -> val;
  58.     }
  59.     ll get(node *&v, ll tl, ll tr, ll k){
  60.         ll tm = (tl + tr) >> 1ll;
  61.         if(tl == tr)
  62.             return tl;
  63.         if((v -> l) == nullptr) v -> l = new node();
  64.         if((v -> r) == nullptr) v -> r = new node();
  65.  
  66.         ll le = (tm - tl + 1) - ((v -> l) -> val);
  67.         if(k <= le)
  68.             return get(v -> l, tl, tm, k);
  69.         else
  70.             return get(v -> r, tm + 1, tr, k - le);
  71.     }
  72. }tr;
  73.  
  74. ll n, q;
  75.  
  76. int main(){
  77.     scanf("%lld %lld", &n, &q);
  78.     for(ll i = 1; i <= q; ++i){
  79.         char t;
  80.         scanf(" %c", &t);
  81.         if(t == 'D'){
  82.             ll x;
  83.             scanf("%lld", &x);
  84.             x = tr.get(tr.root, 1, n, x);
  85.             tr.upd(tr.root, 1, n, x, 1);
  86.         }
  87.         else{
  88.             ll x;
  89.             scanf("%lld", &x);
  90.             printf("%lld\n", tr.get(tr.root, 1, n, x));
  91.         }
  92.     }
  93.     return 0;
  94. }
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Kt9Jo9
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!