fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 2e6+7;
  4. const int mod = 1e9 + 7;
  5. typedef pair<int, int> ii;
  6. typedef pair<int, pair<int, int>> iii;
  7. #define fi first
  8. #define se second
  9. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  10. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  11. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0);
  12. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  13. #define file "main"
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define bat(x, i) (x | (1 << i))
  16.  
  17. int T[maxn];
  18. int n, m, res, kq[maxn];
  19. vector<int> b;
  20.  
  21. void nenso()
  22. {
  23.     sort(b.begin(), b.end());
  24.     b.erase(unique(b.begin(), b.end()), b.end());
  25. }
  26.  
  27. int num(int n)
  28. {
  29.     return lower_bound(b.begin(), b.end(), n) - b.begin() + 1;
  30. }
  31.  
  32. int g_num(int n)
  33. {
  34.     return b[n-1];
  35. }
  36.  
  37. void update(int i, int v)
  38. {
  39.     for (; i<=1e6+5; i += i&(-i)) T[i]=(T[i]+ v);
  40. }
  41. int get(int i)
  42. {
  43.     int res = 0;
  44.     for (; i>0; i -= i&(-i)) res = (T[i]+ res);
  45.     return res;
  46. }
  47.  
  48. struct query
  49. {
  50.     char t;
  51.     int val;
  52.     int l, r, k;
  53. } q[maxn];
  54.  
  55. int cal(int k, int l, int r)
  56. {
  57.     int L = l;
  58.     int res = 2e9;
  59.     if(k > get(r)-get(l-1)) return 0;
  60.     while(l <= r)
  61.     {
  62.         int mid = (l+r) >> 1;
  63.         if(get(mid) - get(L-1) >= k)
  64.         {
  65.             res = mid;
  66.             r = mid-1;
  67.         }
  68.         else l = mid+1;
  69.     }
  70.     return b[res-1];
  71. }
  72.  
  73. int32_t main()
  74. {
  75.     fastIO;
  76.     File(file ".inp", file ".out");
  77.  
  78.     cin >> n;
  79.     For(i, 1, n)
  80.     {
  81.         cin >> q[i].t;
  82.         if(q[i].t == '?')
  83.         {
  84.             cin >> q[i].k>> q[i].l >> q[i].r ;
  85.             b.push_back(q[i].l); b.push_back(q[i].r);
  86.         }
  87.         else cin >> q[i].val, b.push_back(q[i].val);
  88.     }
  89.     nenso();
  90.     For(i, 1, n)
  91.     {
  92.         if(q[i].t == '+')
  93.         {
  94.             update(num(q[i].val), 1);
  95.         }
  96.         else if(q[i].t == '-')
  97.         {
  98.             update(num(q[i].val), -1);
  99.         }
  100.         else
  101.         {
  102.             if(cal(q[i].k, num(q[i].l), num(q[i].r)) == 0) cout << "0\n";
  103.             else cout << cal(q[i].k, num(q[i].l), num(q[i].r)) << '\n';
  104.         }
  105.     }
  106.  
  107. }
  108.  
Success #stdin #stdout 0.01s 9724KB
comments (?)
stdin 
8
+ 1
+ 1
+ 2
? 2 1 10
- 1
? 2 1 10
- 1
? 2 1 10
stdout 
1
2
0
https://ideone.com/vVaqWp
language:
C++14 (clang 8.0)
created:
13 days 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!