记录编号	356788	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.338 s
提交时间	2016-12-06 17:45:32	内存使用	2.61 MiB

#include <cstdio>
#include <cctype>
#define file(x) "cashier." #x
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
namespace I{
	const int L = 1 << 15;
	char buf[L], *s, *t;
	inline char gc() {
		if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
		if (s == t) return EOF;
		return *s++;
	}
	inline char visc() {
		int ch = gc();
		while (!isgraph(ch)) ch = gc();
		return ch;
	}
	inline int gi() {
		int r = 0, ch = gc();
		while (!isdigit(ch)) ch = gc();
		while (isdigit(ch)) r = r*10 + ch - '0', ch = gc();
		return r;
	}
};
using I::visc;
using I::gi;
//namespace Splay {
int fa[N], ch[N][2], sz[N], a[N], c[N], rt, nsz;
int n, bd, ans, f;
inline void up(int o) {if(o) sz[o] = sz[ch[o][0]] + sz[ch[o][1]] + c[o];}
inline int cmp(int o, int x) {
	if (x > a[o]) return 1;
	else if (x < a[o]) return 0;
	else return -1;
}
inline void lk(int d, int s, int p) {
	if(s) fa[s] = p;
	ch[p][d] = s;
}
inline int gd(int o) {
	return ch[fa[o]][1] == o;
}
void rot(int o, int d) {
	int t = ch[o][d];
	lk(gd(o), t, fa[o]);
	lk(d, ch[t][d^1], o);
	lk(d^1, o, t);
	up(o);
	up(t);
}
void splay(int o, int t) {
	while (fa[o] != t) {
		int x = fa[o], y = fa[x], d = ch[x][1] == o, d2 = ch[y][1] == x;
		if (y == t) rot(x, d);
		else if (d == d2) rot(y, d2), rot(x, d);
		else rot(x, d), rot(y, d2);
	}
	if (!t) rt = o;
}

void insert(int o, int v) {
	int d = cmp(o, v);
	if (d == -1) ++c[o], up(o);
	else if (ch[o][d]) insert(ch[o][d], v), up(o), splay(ch[o][d], fa[o]);
	else a[ch[o][d] = ++nsz] = v, fa[nsz] = o, sz[nsz] = c[nsz] = 1, up(o), splay(ch[o][d], fa[o]);
}
int find(int o, int v) {
	if (!o) return 0;
	if (a[o] > v) {
		int x = find(ch[o][0], v);
		if (x && a[x] < a[o]) return x;
		else return o;
	}
	else if (a[o] < v) return find(ch[o][1], v);
	else return o;
}
int kth(int o, int k) {
	while (k <= sz[o]) {
		if (k <= sz[ch[o][1]]) o = ch[o][1];
		else if ((k -= sz[ch[o][1]]) <= c[o]) return a[o];
		else if ((k -= c[o]) <= sz[ch[o][0]]) o = ch[o][0];
		else return -f -1;
	}
	return -f -1;
}
//}
void lmr(int o) {
	if (!o) return;
	lmr(ch[o][0]);
	printf("%d ", a[o] + f);
	lmr(ch[o][1]);
}
int main() {
//#define DBG
	freopen(file(in), "r", stdin);
#ifndef DBG
	freopen(file(out), "w", stdout);
#endif
	a[0] = -INF;
	n = gi(), bd = gi();
	int wtf = 0;
	while (n--) {
		char cmd = visc();
		int v = gi();
		if (cmd == 'I') {
			if (v < bd) {
				++ans;
				continue;
			}
			else insert(rt, v - f), ++wtf;
		}
		else if (cmd == 'A') f += v;
		else if (cmd == 'S') {
			f -= v;
			int p = find(rt, bd - f);
			if (!p) {
				ans += sz[rt];
				rt = 0;
				ch[0][1] = 0;
				continue;
			} 
			splay(p, 0);
			ans += sz[ch[p][0]];
			ch[p][0] = 0;
			up(p);
		}	
		else printf("%d\n", kth(rt, v) + f);
#ifdef DBG
		puts("");
		lmr(rt);
		puts("");
#endif
	}
//	printf("%d", ans);
		printf("%d", wtf - sz[rt]);
}