fork download
  1. //Collecting the dream I threw away
  2. //Road to VOI
  3. #include<bits/stdc++.h>
  4. #define el '\n'
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define fumo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  8. #define pb push_back
  9. #define str string
  10. #define sz(v) (int)v.size()
  11. #define ldb long double
  12. #define db double
  13. #define reimu(v) v.begin(), v.end()
  14. #define ret return
  15. #define fi first
  16. #define se second
  17. #define int long long
  18. using namespace std;
  19. #pragma GCC optimize ("Ofast")
  20. #pragma GCC optimize ("unroll-loops")
  21. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  22. //ᗜˬᗜ
  23. const int N=2e5+7,base=37,block=280;
  24. const ll mod=1e9+7,inf=1e18;
  25. int n,lim;
  26. int bit[N];
  27. const int offset=1e5;
  28. priority_queue<int, vector<int>, greater<int>> pq;
  29. int delta,cntadd;
  30.  
  31. void update(int idx, int val)
  32. {
  33. for(;idx<=1e5+offset;idx+=idx & (-idx)) bit[idx]+=val;
  34. }
  35.  
  36. int getpoint(int idx)
  37. {
  38. int ans=0;
  39. for(;idx;idx-=idx & (-idx)) ans+=bit[idx];
  40. ret ans;
  41. }
  42.  
  43. int getrange(int l, int r)
  44. {
  45. ret getpoint(r)-getpoint(l-1);
  46. }
  47.  
  48. bool check(int mid, int k)
  49. {
  50. ret getrange(mid+offset, 1e5+offset)>=k;
  51. }
  52.  
  53. void process(char op, int k)
  54. {
  55. if(op=='I')
  56. {
  57. cntadd++;
  58. int x=k-delta;
  59. pq.push(x);
  60. update(x+offset, 1);
  61. }
  62. if(op=='A') delta+=k;
  63. if(op=='S') delta-=k;
  64. while(!pq.empty() && pq.top()+delta<lim)
  65. {
  66. update(pq.top()+offset, -1);
  67. pq.pop();
  68. }
  69. if(op=='F')
  70. {
  71. if(sz(pq)<k)
  72. {
  73. cout<<-1<<el;
  74. ret;
  75. }
  76. int ans=-1;
  77. int l=-1e5,r=1e5;
  78. while(l<=r)
  79. {
  80. int mid=l+((r-l)>>1);
  81. if(check(mid, k))
  82. {
  83. ans=mid;
  84. l=mid+1;
  85. }
  86. else r=mid-1;
  87. }
  88. cout<<ans+delta<<el;
  89. }
  90. }
  91.  
  92. void sol()
  93. {
  94. cin>>n>>lim;
  95. for(int i=1;i<=n;++i)
  96. {
  97. char op;
  98. int k;
  99. cin>>op>>k;
  100. process(op, k);
  101. }
  102. cout<<cntadd-sz(pq)<<el;
  103. }
  104.  
  105. void ffopen(const str &alice)
  106. {
  107. if(fopen((alice+".inp").c_str(), "r")){
  108. freopen((alice+".inp").c_str(), "r", stdin);
  109. freopen((alice+".out").c_str(), "w", stdout);
  110. }
  111. }
  112.  
  113. signed main()
  114. {
  115. fumo
  116. ffopen("");
  117. int t=1;
  118. //cin>>t;
  119. while(t--) sol();
  120. ret 0;
  121. }
  122.  
Success #stdin #stdout 0s 560KB
stdin
Standard input is empty
stdout
0