fork download 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16. #include <tuple>
  17.  
  18. #define MAX 300010
  19. #define PRIME 31
  20. #define INC 100000
  21. #define MOD 1000000007
  22. #define PI 3.1415926535897932384
  23. #define F first
  24. #define S second
  25. #define pb push_back
  26. #define mp make_pair
  27. typedef long long ll;
  28.  
  29. struct node{
  30.     int s, e;
  31.     int cont;
  32. };
  33.  
  34. int t, m, least, d, lft;
  35. node tree[5*MAX];
  36.  
  37. void build(int s, int e, int pos){
  38.     int mid = s+(e-s)/2;
  39.     tree[pos].s = s; tree[pos].e = e;
  40.     tree[pos].cont = 0;
  41.  
  42.     if(s < e){
  43.         build(s, mid, 2*pos);
  44.         build(mid+1, e, 2*pos+1);
  45.     }
  46. }
  47.  
  48. // op: {0, 1} = {reset cont in range, cont += 1}
  49. int update(int s, int e, bool op, int pos){
  50.     int dec, mid = tree[pos].s+(tree[pos].e-tree[pos].s)/2;
  51.  
  52.     if(tree[pos].s == tree[pos].e) dec = tree[pos].cont;
  53.     else if(mid >= e) dec = update(s, e, op, 2*pos);
  54.     else if(mid < s) dec = update(s, e, op, 2*pos+1);
  55.     else dec = update(s, mid, op, 2*pos)+update(mid+1, e, op, 2*pos+1);
  56.  
  57.     if(op) tree[pos].cont += 1;
  58.     else tree[pos].cont -= dec;
  59.  
  60.     // How many people left
  61.     return dec;
  62. }
  63.  
  64. // Find the K-th bigger wage
  65. int query(int num, int pos){
  66.  
  67.     // Not enough workers
  68.     if(num > tree[pos].cont) return MOD*(-1);
  69.  
  70.     if(tree[pos].s == tree[pos].e) return tree[pos].s;
  71.     if(tree[2*pos+1].cont < num) return query(num-tree[2*pos+1].cont, 2*pos);
  72.     return query(num, 2*pos+1);
  73. }
  74.  
  75. int main(){
  76.     //freopen("in.txt", "r", stdin);
  77.  
  78.     cin >> t;
  79.     while(t--){
  80.  
  81.         cin >> m >> least;
  82.  
  83.         build(0, MAX-1, 1);
  84.         d = 0; lft = 0;
  85.  
  86.         char c; int k;
  87.         for(int i = 0;i < m;i++){
  88.             scanf(" %c %d", &c, &k);
  89.  
  90.             if(c == 'I'){
  91.                 if(k >= least) update(INC+k-d, INC+k-d, true, 1);
  92.             }
  93.             else if(c == 'A') d += k;
  94.             else if(c == 'S'){
  95.                 if(!k) continue;
  96.                 lft += update(INC+least-d, INC+least-d+k-1, false, 1);
  97.                 d -= k;
  98.             }
  99.             else{
  100.                 int temp = query(k, 1);
  101.                 if(temp != MOD*(-1)) temp += d;
  102.                 else temp = INC-1;
  103.                 printf("%d\n", temp-INC);
  104.             };
  105.         }
  106.  
  107.         printf("%d\n", lft);
  108.     }
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 21040KB
comments (?)
stdin 
1
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
stdout 
10
20
-1
2
https://ideone.com/XstiAL
language:
C++14 (gcc 8.3)
created:
10 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!