why?在洛谷在线运行以下
7 0
I 8
I 10
I 12
S 10
F 1
S 2
F 1
代码的时候输出了个0??? 然后把cout改成了write()函数就过了??? 所以cout是有bug吗QAQ
//#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define bug(x) cout << #x << " = " << x << '\n';
using namespace std;
#define ll int
#define dd double
#define endl '\n'
#define pll pair<ll,ll>
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline bool read(ll& x) {
x = 0;
char c = getchar();
if (c == EOF)return false;
else if (c == '}')return 0;
while (c > '9' || c < '0')c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return true;
}
template<class T>void unwrite(T x) {
if (x > 9) unwrite(x / 10);
putchar(x % 10 + '0');
}
template<class T>inline void write(T x) {
x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
}
template<class T>inline void write(T x, char&& c) {
x < 0 ? putchar('-'), unwrite(0 - x) : unwrite(x);
putchar(c);
}
//void solve()
//{
// ll dp[1003], inf = -1, len = 10, a[100];
//
// for (int i = 0; i < len; ++i)a[i] = read();
//
// fill(dp, dp + len, inf);
//
// for (int i = 0; i < len; ++i)
// *lower_bound(dp, dp + len, a[i]) = a[i];
//
// for (int i = 0; i < len; ++i)write(dp[i], ' ');
//
// putchar('\n');
//
// write(lower_bound(dp, dp + len, inf) - dp, '\n');
//}
//
//priority_queue<ll, vector<ll>, greater<ll>> B;
//priority_queue<ll, vector<ll>, greater<ll>> xiao;
//priority_queue<ll> da;
inline ll max(ll a, ll b) {
return a > b ? a : b;
}
inline ll min(ll a, ll b) {
return a < b ? a : b;
}
ll pow(ll di, ll zhi, ll mod = 1e9 + 7) {
ll ans = 1;
for (di %= mod; zhi != 0; zhi >>= 1) {
if (zhi & 1)ans = ans * di % mod;
di = di * di % mod;
}
return ans;
}
ll gcd(ll a, ll b) {
if (a < b)swap(a, b);
for (ll c = 0; b != 0; b = c % b)c = a, a = b;
return a;
}
// a * x + b * y = gcd(a, b)
ll Exgcd(ll a, ll b, ll& x, ll& y) {
if (!b) {
x = 1;
y = 0;
return a;
}
ll d = Exgcd(b, a % b, x, y), t = x;
x = y;
y = t - (a / b) * y;
return d;
}
// ------------------------------------------------
const ll inf = 1e16 + 7ll, mod = 1e9 + 7ll, N = 1e5 + 3;
/*
权值线段树 + 离散化 + 双向函数映射
*/
struct node {
ll l = 0, r = 0, v = inf, ge = 0, kai = 0;
};
ll n, m, i, j, k, kk, y, len, llen, add, kai;
struct nnnn {
char cc; ll k;
}A[300005];
map<ll, ll>B;
ll C[300005];
vector<node>D;
void out() {
cout << "\ni l r g v k\n";
for (ll i = 1; i < len << 1; ++i)
cout << i << ' ' << D[i].l << ' ' << D[i].r << ' ' << D[i].ge << ' ' << D[i].v << ' ' << D[i].kai << endl;
}
void bulid() {
for (len = llen << 1; len != (-len & len); len -= -len & len); D.resize(len << 1);
for (i = 0; i < len; ++i)D[i + len].l = D[i + len].r = D[i + len].v = i + 1;
for (i = len - 1; i > 0; --i)
D[i].l = D[i << 1].l, D[i].r = D[i << 1 | 1].r,
D[i].v = D[i << 1 | 1].v;
//out();
}
inline void spread(ll k) {
if (D[k].kai) {
D[k].ge = D[k].kai = 0;
if (k < len)
D[k << 1].kai = D[k << 1 | 1].kai = 1;
}
}
void cz1() {
for (j = 1; j < len;) {
spread(j);
++D[j].ge;
j <<= 1;
if (D[j].v < kk)j |= 1;
}
if (D[j].kai)D[j].ge = 1, D[j].kai = 0;
else ++D[j].ge;
}
//[1, y)
ll cz3(ll k) {
//bug(k);
if (D[k].l >= y || D[k].kai)return 0;
else if (D[k].r < y)
return D[k].kai = 1, D[k].ge;
else{
ll ans = cz3(k << 1) + cz3(k << 1 | 1);
D[k].ge -= ans;
return ans;
}
}
void cz4(ll k) {
//bug("++++++++++++++++++++++++");
while (k < len) {
k <<= 1;
spread(k);
spread(k | 1);
if (D[k | 1].ge >= kk)k |= 1;
else kk -= D[k | 1].ge;
}
cout << C[k - len + 1] + add << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (n = read(), m = read(); i < n; ++i) {
cin >> A[i].cc >> A[i].k;
if (A[i].cc == 'A')add += A[i].k;
else if (A[i].cc == 'S')add -= A[i].k, B[m - add] = 0;
else if (A[i].cc == 'I')A[i].k -= add, B[A[i].k] = 0;
}
for (auto& x : B)x.second = ++llen, C[llen] = x.first;
//for (i = 1; i <= llen; ++i)cout << C[i] << ' '; cout << endl;
bulid(); add = 0;
for (i = 0; i < n; ++i) {
//cout << A[i].cc << ' ' << A[i].k << endl;
switch (A[i].cc)
{
case 'I':
if (A[i].k + add >= m) kk = B[A[i].k], cz1();
break;
case 'A':
add += A[i].k;
break;
case 'S':
add -= A[i].k;
y = B[m - add];
kai += cz3(1);
break;
case 'F':
kk = A[i].k;
if (D[1].ge < kk)cout << -1 << endl;
else cz4(1);
break;
default:
break;
}
//out();
}
cout << kai << endl;
}
inline void out2(double ans) {
printf("%.2lf", ans);
}
/*
11 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
I 50
I 0
9 10
I 30
I 40
I 50
S 35
F 2
A 35
I 20
F 2
F 1
--
-1 20 50 2
11 10
I 30
I 30
I 30
S 20
I 20
F 1
F 2
A 10
S 15
F 2
F 1
--
20 10 -1 15 3
5 5
A 10
A 20
I 3
I 5
F 1
--
5 0
5 20
A 10000000
A 10000000
I 5
I 4
F 1
--
-1 0
10 10
I 50
I 100
I 70
S 40
A 20
F 2
I 5
A 10
F 3
S 10000
--
50 40 3
5 3
I 2
I 1
I 3
A 10
F 1
--
13 0
7 0
I 8
I 10
I 12
S 10
F 1
S 2
F 1
--
2 0 2
*/