记录编号	149424	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.422 s
提交时间	2015-02-24 10:57:42	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
//tree<LL,null_type,greater<LL>,rb_tree_tag,tree_order_statistics_node_update> T,TE;
tree<LL,null_mapped_type,greater<LL>,rb_tree_tag,tree_order_statistics_node_update> T,TE;
int main(){
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	int N;
	int mn,dlt=0;
	LL x;
	scanf("%d%d",&N,&mn);
	char cmd[10];
	int cnt=0,leave=0;
	for(int i=1;i<=N;i++){
		scanf("%s%lld",cmd,&x);
		if(cmd[0]=='I'){
			if(x>=mn){
				x-=dlt;
				cnt++;
				T.insert((x<<20)+i);
			}
		}
		else if(cmd[0]=='A') dlt+=x;
		else if(cmd[0]=='S'){
			dlt-=x;
			LL low=mn-dlt,now=cnt-T.order_of_key(low<<20);
			cnt-=now,leave+=now;
			T.split(low<<20,TE);
		}
		else if(cmd[0]=='F'){
			if(x<=cnt) printf("%lld\n",(*T.find_by_order(x-1)>>20)+dlt);
			else printf("-1\n");
		}
	}
	printf("%d\n",leave);
	return 0;
}