fork download
copy 
  1. //  #include <bits/stdc++.h>
  2.  
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #include <string>
  9. #include <string.h>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <map>
  13. #include <vector>
  14. #include <set>
  15. #include <queue>
  16. #include <climits>
  17. #include <ctime>
  18.  
  19. #include <unordered_map>
  20.  
  21. #define pb push_back
  22. #define ppb pop_back
  23. #define mp make_pair
  24.  
  25. #define ll long long
  26. #define ld long double
  27. #define uns unsigned
  28.  
  29. #define F first
  30. #define S second
  31.  
  32. #define sz(x) (int)x.size()
  33. #define str(x) (int)strlen(x)
  34. #define all(x) x.begin(), x.end()
  35. #define sqr(x) ((x) * (x))
  36. #define bit(x) __builtin_popcountll(x)
  37.  
  38. #define itr ::iterator
  39.  
  40. #define rt return
  41. #define sf scanf
  42. #define pf printf
  43. #define nl '\n'
  44.  
  45. #define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)
  46. #define SABR inline ll IN(){ll x=0,ch=getchar(),f=1;while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();if (ch=='-'){f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}inline void OUT(ll x){if (x<0) putchar('-'),x=-x;if (x>=10) OUT(x/10),putchar(x%10+'0');else putchar(x+'0');}
  47. #define ios ios_base::sync_with_stdio(0);
  48.  
  49. #define int long long
  50.  
  51.                                                                                                                                                                                                             #define                                                                                                                                                                             int long long
  52. #define NeverGiveUp main
  53.  
  54. #define Memset(x, y, n) for (int mmst = 1; mmst <= n; mmst++) x[mmst] = y;
  55.  
  56. #define sp system("pause");
  57.  
  58. #define Fname "inverse"
  59. #define RockyBalboa
  60. //#define TNT
  61.  
  62. using namespace std;
  63.  
  64. typedef pair <int, int> pi;
  65. typedef vector <int> vi;
  66. typedef pair <double, double> pd;
  67.  
  68. const int N = (int)1e5 + 17;
  69. const int MX = (int) 1e6 + 17;
  70. const int MOD = (int) 1e9 + 7;
  71. const ll oo = LLONG_MAX;
  72. const int INF = INT_MAX;
  73. const ld Pi = 3.14159265358979323846264338327950288419716939937510;
  74.  
  75. const int di[4] = {-1, 0, 1, 0};
  76. const int dj[4] = {0, 1, 0, -1};
  77.  
  78.     void IOI2017(){
  79.     #ifdef RockyBalboa
  80.         freopen(Fname".in", "r", stdin);
  81.         freopen(Fname".out", "w", stdout);
  82.     #endif
  83.     #ifdef TNT
  84.         freopen("input.txt", "r", stdin);
  85.         freopen("output.txt", "w", stdout);
  86.     #endif
  87.     }
  88.     SABR
  89.  
  90.     const int sz = 200002;
  91.  
  92.     int n;
  93.     pi t[sz * 4], x[sz];
  94.     vector <pi> cmp;
  95.     pair <char, int> in[2 * N];
  96.     inline void Update(int pos, pi val, int v = 1, int tl = 1, int tr = sz){
  97.         if (tl == tr) t[v] = val;
  98.         else{
  99.             int tm = tl + tr >> 1;
  100.             if (pos <= tm) Update(pos, val, v + v, tl, tm);
  101.             else Update(pos, val, v + v + 1, tm + 1, tr);
  102.             t[v].F = t[v + v].F + t[v + v + 1].F;
  103.         }
  104.     }
  105.     inline int Get(int l, int r, int v = 1, int tl = 1, int tr = sz){
  106.         if (l <= tl && tr <= r) rt t[v].F;
  107.         if (tl > r || tr < l) rt 0;
  108.         int tm = tl + tr >> 1;
  109.         rt Get(l, r, v + v, tl, tm) + Get(l, r, v + v + 1, tm + 1, tr);
  110.     }
  111.     inline int Kth(int k, int v = 1, int tl = 1, int tr = sz){
  112.         if (tl == tr) rt t[v].S;
  113.         int tm = tl + tr >> 1;
  114.         if (t[v + v].F >= k) rt Kth(k, v + v, tl, tm);
  115.         else rt Kth(k - t[v + v].F, v + v + 1, tm + 1, tr);
  116.     }
  117. NeverGiveUp(){
  118.     ios
  119.     cin >> n;
  120.     for (int i = 1; i <= n; i++){
  121.         cin >> in[i].F >> in[i].S;
  122.         if (in[i].F != 'K')
  123.             cmp.pb({in[i].S, i});
  124.     }
  125.     sort(all(cmp));
  126.     for (int i = 0, j = 1; i < sz(cmp); i++){
  127.         if (i > 0 && cmp[i].F != cmp[i - 1].F) j++;
  128.         x[cmp[i].S] = {j, cmp[i].F};
  129.     }
  130.     for (int i = 1; i <= n; i++){
  131.         if (in[i].F == 'I') Update(x[i].F, {1, x[i].S});
  132.         if (in[i].F == 'C') cout << Get(0, x[i].F - 1) << nl;
  133.         if (in[i].F == 'D') Update(x[i].F, {0, 0});
  134.         if (in[i].F == 'K'){
  135.             if (t[1].F < in[i].S) cout << "invalid\n";
  136.             else cout << Kth(in[i].S) << nl;
  137.         }
  138.     }
  139.  
  140.  
  141.     rt 0;
  142. }
  143.  
Success #stdin #stdout 0s 21440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/n4L51O
language:
C++14 (gcc 8.3)
created:
8 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!