记录编号	424101	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.347 s
提交时间	2017-07-12 20:33:34	内存使用	1.84 MiB

#include<iostream>
#include<stdio.h>
using namespace std;
#define maxn 100001
struct node
{
	int lc,rc;
	int size,w;
	void init()
	{
		lc=rc=0;size=1;
	}
}tree[maxn];
int cnt,root;
void update(int &x)
{
	tree[x].size=tree[tree[x].lc].size+tree[tree[x].rc].size+1;
}
void l_(int &x)
{
	int y=tree[x].rc;
	tree[x].rc=tree[y].lc;tree[y].lc=x;
	tree[y].size=tree[x].size;update(x);
	x=y;
}	
void r_(int &x)
{
	int y=tree[x].lc;
	tree[x].lc=tree[y].rc;tree[y].rc=x;
	tree[y].size=tree[x].size;update(x);
	x=y;
}
void MAINTAIN(int &x,bool flag)
{
	if(flag==0)
	{
		if(tree[tree[tree[x].lc].lc].size>tree[tree[x].rc].size)
			r_(x);
		else
			if(tree[tree[tree[x].lc].rc].size>tree[tree[x].rc].size)
				l_(tree[x].lc),r_(x);
			else
				return ;	
	}
	else
	{
		if(tree[tree[tree[x].rc].rc].size>tree[tree[x].lc].size)	
			l_(x);
		else
			if(tree[tree[tree[x].rc].lc].size>tree[tree[x].lc].size)	
				r_(tree[x].rc),l_(x);
			else
				return ;
	}
	MAINTAIN(tree[x].lc,0);
	MAINTAIN(tree[x].rc,1);
	MAINTAIN(x,0);
	MAINTAIN(x,1);
}
void insert(int &x,int w)
{
	if(x==0)
	{
		x=++cnt;
		tree[x].init();
		tree[x].w=w;
	}
	else
	{
		++tree[x].size;
		if(w<tree[x].w)
			insert(tree[x].lc,w);
		else
			insert(tree[x].rc,w);
		MAINTAIN(x,w>=tree[x].w);
	}
}
int Delete()
{
	int t=root;
	if(tree[t].lc==0)
	{
		root=tree[root].rc;
		return tree[t].w;
	}
	while(tree[tree[t].lc].lc)
	{
		--tree[t].size;
		t=tree[t].lc;
	}
	--tree[t].size;
	int ans=tree[tree[t].lc].w;
	tree[t].lc=tree[tree[t].lc].rc;
	return ans;
}
int getmin(int t)
{
	while(tree[t].lc)
		t=tree[t].lc;
	return t;
}
int kth(int &x,int k)
{
	if(k<=tree[tree[x].lc].size)	
		return kth(tree[x].lc,k);
	if(k>tree[tree[x].lc].size+1)
		return kth(tree[x].rc,k-tree[tree[x].lc].size-1);
	return tree[x].w;
}
int n,m;
int flag,ans;
int main()
{
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	int x;
	char s[6];
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s%d",s,&x);
		switch(s[0])
		{
			case 'I':
				if(x>=m)insert(root,x-flag);
				break;
			case 'A':
				flag+=x;
				break;
			case 'S':
				flag-=x;
				while(root!=0&&tree[getmin(root)].w+flag<m)
					Delete(),++ans;
				break;
			case 'F':
				if(root==0||tree[root].size<x)
					printf("-1\n");
				else
					printf("%d\n",kth(root,tree[root].size-x+1)+flag);
		}
	}
	printf("%d",ans);
}