fork(1) download
copy 
  1. /*And I thought my jokes were bad*/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <iostream>
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define ll long long
  9. #define dbg puts("Viva la vida");
  10. #define CHECK(x) cout << (#x) << " is " << (x) << endl;
  11. #define nl puts("");
  12. typedef map<int,int> mii;
  13. typedef map<string,int> msi;
  14. typedef pair<int,int> pii;
  15. typedef pair<int,pii > tii;
  16. typedef vector <int> VI;
  17. typedef vector<ll> VL;
  18. typedef set<int> SI;
  19. #define mp make_pair
  20. #define pb push_back
  21. #define IN(x) scanf("%d",&x);
  22. #define INL(x) scanf("%lld",&x);
  23. #define OUT(x) printf("%d",x);
  24. #define OUTL(x) printf("%lld",x);
  25. #define SP printf(" ");
  26. #define X first
  27. #define Y second
  28. #define SZ(_a) (int)_a.size()
  29. #define ALL(_a) _a.begin(),_a.end()
  30. #define EPS 1e-9
  31. #define PI acos(-1.0)
  32. #define MAX 200005
  33. #define MOD 1000000007
  34. #define INF (1 << 31)
  35.  
  36. /*
  37. Like memories in cold decay
  38. Transmissions echoing away
  39. Far from the world of you and I
  40. Where oceans bleed into the sky
  41. */
  42. vector<int> sh;
  43. vector<pii > viva;
  44. int tree[3*MAX];
  45. map<int,int> ind,cntr;
  46. void update(int n,int l,int r,int i,int v)
  47. {
  48.     if(i>r)
  49.         return ;
  50.     if(i<l)
  51.         return ;
  52.     if(l==r&&l==i)
  53.     {
  54.         tree[n]=v;
  55.         return ;
  56.     }
  57.     int mid=l+r;
  58.     mid/=2;
  59.     update(2*n,l,mid,i,v);
  60.     update(2*n+1,mid+1,r,i,v);
  61.     tree[n]=tree[2*n]+tree[2*n+1];
  62.     return ;
  63.  
  64. }
  65. int query(int n,int l,int r,int i,int j)
  66. {
  67. //    cout<<i<<' '<<j<<endl;
  68.     if(i>r||j<l)
  69.         return 0;
  70.     if(i<=l&&j>=r)
  71.         return tree[n];
  72.     int mid=l+r;
  73.     mid/=2;
  74.     return query(2*n,l,mid,i,j)+query(2*n+1,mid+1,r,i,j);
  75. }
  76. int query_2(int n,int l,int r,int val)
  77. {
  78. //    cout<<l<<' '<<r<<' '<<val<<endl;
  79.     if(tree[n]<val)
  80.         return -1;
  81.     if(l==r)
  82.     {
  83.         return l;
  84.     }
  85.     int mid=l+r;
  86.     mid/=2;
  87.     if(tree[2*n]>=val)
  88.         return query_2(2*n,l,mid,val);
  89.     else
  90.         return query_2(2*n+1,mid+1,r,val-tree[2*n]);
  91. }
  92. int main()
  93. {
  94. 	int i,j,k,n,m,p,q,t,x,y;
  95. 	char ch;
  96. 	cin>>n;
  97.     for (i=0;i<n;i++)
  98.     {
  99.         cin>>ch>>x;
  100.         viva.pb(mp(ch,x));
  101.             sh.pb(x);
  102.     }
  103.     unique(sh.begin(),sh.end());
  104.     sort(sh.begin(),sh.end());
  105.     for (i=0;i<sh.size();i++)
  106.     {
  107.         ind[sh[i]]=i;
  108.     }
  109.     for (i=0;i<n;i++)
  110.     {
  111.         ch=viva[i].first;
  112.         x=viva[i].second;
  113.         if(ch=='I')
  114.         {
  115. //            cout<<"INSERT"<<endl;
  116. //            CHECK(x)
  117. //            CHECK(ind[x]);
  118.             if(!cntr[x])
  119.             {
  120.                 update(1,0,n,ind[x],1);
  121.                 cntr[x]++;
  122.             }
  123.         }
  124.         else if(ch=='D')
  125.         {
  126.             if(cntr[x])
  127.             {
  128.                 update(1,0,n,ind[x],0);
  129.             }
  130.         }
  131.         else if(ch=='C')
  132.         {
  133.             cout<<query(1,0,n,0,ind[x]-1)<<endl;
  134.         }
  135.         else if(ch=='K')
  136.         {
  137.             k=query_2(1,0,n,x);
  138.             if(~k)
  139.             cout<<sh[k]<<endl;
  140.             else
  141.                 cout<<"invalid"<<endl;
  142.         }
  143.     }
  144. 	return 0;
  145. }
  146.  
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
66
I 4220
I 42
K 74419
I 54
I 1241
I 1
I 1
I 3
I 207
I 170154
K 7
I 10791
I 4
I 32
I 5463540
I 235
I 47
I 8
I 4
K 248
I 63794
I 16
K 19
I 83
D 5
I 28
I 88
C 308
I 0
I 48
K 1
I 2183
I 39
I 28
K 467159645
I 0
C 6
I 20
I 22
C 4
C 15217947
I 546879
I 710297
I 1416
I 888
I 2
I 1
I 6
I 7535
D 4
K 1664
I 41
I 5717764
C 0
D 1
C 441
I 335
I 4493003
I 1756
K 1
I 495861
I 1
I 29
I 3
D 6
K 5
stdout
copy 
invalid
4220
invalid
invalid
14
0
invalid
4
3
26
invalid
0
20
0
16
https://ideone.com/S1LK4A
language:
C++14 (gcc 8.3)
created:
4 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!