[NOI 2004]郁闷的出纳员 - /k - 176782

记录编号	176782	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.582 s
提交时间	2015-08-09 20:32:47	内存使用	2.09 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct u
{
	int z;
	int y;
	int zz;
	int rk;
	int d;
	int s;
}c[100000+10];
int f[100000+10],rr,n,m,rt,p,gd,dm,mn;
/****************************************************************/
void gy(int x)
{   
	c[0].s=0;
	int y=f[x];
	if(c[x].s+c[y].d+c[c[y].y].s!=c[y].s)
		printf("&&&&&&&&&&&&&**************************&&&&&&&&&&&&&&&&&&&&&&&&");
	int uuu=c[y].s;
	/*if(p==3)
		printf("\nuuuu%duuu\n",uuu);*/
	if(f[y]!=0)
	{
		if(c[f[y]].z==y)
			c[f[y]].z=x;
		else
			c[f[y]].y=x;
	}
	f[x]=f[y];
	if(y==rt)
	{	
		rt=x;
		f[x]=0;
	}
	//c[x].s+=c[c[y].y].s+c[y].d;
	//c[y].s-=c[c[x].z].s+c[x].d;
	c[0].s=c[0].d=0;
	f[y]=x;
	if(c[y].z!=0)
		c[y].z=c[x].y;
	if(c[x].y!=0)
		f[c[x].y]=y;
	c[x].y=y;
	c[y].s=c[y].d+c[c[y].z].s+c[c[y].y].s;
	c[x].s=c[x].d+c[c[x].z].s+c[c[x].y].s;
	if(c[x].s!=uuu)
		printf("SDFGDFGDSFGDFSGDSFGDSF!!!!!!!!!!!!!!!!!!!!\n");
}
void gz(int y)
{
	int x=f[y];
	if(f[x]!=0)
	{
		if(c[f[x]].z==x)
			c[f[x]].z=y;
		else
			c[f[x]].y=y;
	}
	f[y]=f[x];
	if(x==rt)
	{
		rt=y;
		f[y]=0;
	}
	f[x]=y;
	c[0].s=c[0].d=0;
	//c[x].s-=c[c[y].y].s+c[y].d;
	//c[y].s+=c[c[x].z].s+c[x].d;
	c[x].y=c[y].z;
	f[c[x].y]=x;
	c[y].z=x;
	c[x].s=c[x].d+c[c[x].z].s+c[c[x].y].s;
	c[y].s=c[y].d+c[c[y].z].s+c[c[y].y].s;
}
//**********************************************9**********************/
void gch(int x,int k)
{
	//printf("ch");
	c[x].s++;
	if(k==c[x].zz+dm)
	{
		c[x].d++;
		p=0;
		return ;
	}
	if(k<c[x].zz+dm)
	{
		if(c[x].z==0)
		{
			c[x].z=++n;
			c[n].zz=k-dm;
			f[n]=x;
			c[n].s=1;
			c[n].d=1;
			c[n].rk=rand();
			p=n;
			return ;
		}
		else
			gch(c[x].z,k);
	}
	if(k>c[x].zz+dm)
	{
		if(c[x].y==0)
		{
			c[x].y=++n;
			c[n].zz=k-dm;
			f[n]=x;
			c[n].d=1;
			c[n].s=1;
			c[n].rk=rand();
			p=n;
			return ;
		}	
		else
			gch(c[x].y,k);
	}
	return ;
}
void grk(int a)
{
	//printf("rk");
	c[0].s=0;
	int p=0;
	if(c[a].s==c[a].d+c[c[a].z].s+c[c[a].y].s)
		p=1;
		//printf("wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww");
	if(a==rt||c[a].rk>=c[f[a]].rk)
		return ;
	//printf("klj\n\n\n");
	//printf("GFGDf");
	if(c[f[a]].z==a)
	{
		if(f[a]==rt)
		{
			gy(a);
			rt=a;
			f[a]=0;
			return ;
		}
		gy(a);
		grk(a);
			///////////////////
	if(c[a].s!=c[a].d+c[c[a].z].s+c[c[a].y].s)
		p++;
	//	if(p==2)
	//	printf("wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww");
		///////////////////////
		return;
	}	
	if(c[f[a]].y==a)
	{
		if(f[a]==rt)
		{
			gz(a);
			rt=a;
			f[a]=0;
			return ;
		}
		gz(a);
		grk(a);
	}	
}
int gdl(int a)
{
	if(a==0)
	{
		return 0;
	}
	int u=0;
	if(c[a].zz+dm<mn)
	{
		if(c[a].z!=0)
			u+=c[c[a].z].s;
		u+=c[a].d;
		rr-=u;
		gd+=u;
		if(rt==a)
		{
			rt=c[a].y;
		}
		if(c[a].y!=0)
			f[c[a].y]=f[a];
		if(f[a]!=0)
		{
			if(c[f[a]].z==a)
				c[f[a]].z=c[a].y;
			else
				c[f[a]].y=c[a].y;
		}
		if(c[a].y!=0)
			u+=gdl(c[a].y);
		f[a]=c[a].z=c[a].y=c[a].zz=c[a].s=0;
		return u;
	}
	if(c[a].z!=0)
	{
		u+=gdl(c[a].z);
	}
	c[a].s-=u;
	return u;
}
void gw(int h,int k)
{
	//printf("w");
	c[0].s=0;
	/*if(c[h].s!=c[c[h].z].s+c[c[h].y].s+c[h].d)
			printf("wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww\n");*/
	if(h==0)
		return;
	int u=0;
	if(c[h].y!=0)
	{
		u+=c[c[h].y].s;
	}
	if(k<=u)
	{	
		gw(c[h].y,k);
		return;
	}
	if(u+c[h].d>=k)
	{
		printf("%d\n",c[h].zz+dm);
		return;
	}
	if(c[h].z!=0)
	if(u+c[h].d<k&&k<=u+c[h].d+c[c[h].z].s)
	{
		gw(c[h].z,k-u-c[h].d);
		return;
	}
	printf("DF\n");	
}
bool gff(int a)
{
	while(f[a]!=0)
		a=f[a];
	if(a==rt)
		return 1;
		return 0;
}
void gt()
{
	printf("\n%d\n",rt);
	printf("i z y zz rk s f\n");
	for(int i=1;i<=n;i++)
	{
		if(gff(i))
			printf("%d %d %d %d %d %d %d\n",i,c[i].z,c[i].y,c[i].zz+dm,c[i].rk,c[i].s,f[i]);
	}
}
int main()
{
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	scanf("%d%d",&m,&mn);
	//printf("%d %d\n",m,mn);
	//lmin=mn;
	char ml[10];
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%s%d",ml,&k);
		//printf("%c %d\n",ml[0],k);
		if(ml[0]=='I')
		{
			if(k>=mn)
			{
				++rr;  //人数++ 
				if(rt==0)
				{
					c[++n].zz=k-dm;
					c[n].rk=rand();
					rt=n;
					c[n].d=c[n].s=1;  
				}
				else
				{
					gch(rt,k);
					//printf("GF%d",p);
					if(p!=0)
						grk(p);
						//if(p==3)
					//		printf("GDFGDFG\n");
				}		
			}
			//continue;
		}
		if(ml[0]=='A')
		{
			dm+=k;
			//continue;
		}
		if(ml[0]=='S')
		{
			dm-=k;
			if(rt!=0)
				gdl(rt);
			//continue;
		}
		if(ml[0]=='F')
		{
			if(rr<k)
				printf("-1\n");
			else
				gw(rt,k);
		}
		//gt();
	}
	printf("%d",gd);
	//while(1);
}