Cod sursa(job #518956)

Utilizator blastoiseZ.Z.Daniel blastoise Data 3 ianuarie 2011 16:42:27
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>

struct tree
{
	int Q,L,R;
}T[262144];

int N,P,x,y,i,c;

inline void update(int nod,int L,int R)
{
	int M=(L+R)/2;

	if(x<=L&&R<=y)
	{
		if(c==1)
		{
			T[nod].Q=0;
			T[nod].L=0;
			T[nod].R=0;
		}
		else
		{
			T[nod].Q=R-L+1;
			T[nod].L=R-L+1;
			T[nod].R=R-L+1;
		}
	}
	else
	{
		if(T[nod].Q==R-L+1)
		{
			T[nod<<1].Q=M-L+1;
			T[nod<<1].L=M-L+1;
			T[nod<<1].R=M-L+1;
			T[(nod<<1)+1].Q=R-M;
			T[(nod<<1)+1].L=R-M;
			T[(nod<<1)+1].R=R-M;
		}
		else
		if(T[nod].Q==0)
		{
			T[nod<<1].Q=0;
			T[nod<<1].L=0;
			T[nod<<1].R=0;
			T[(nod<<1)+1].Q=0;
			T[(nod<<1)+1].L=0;
			T[(nod<<1)+1].R=0;
		}

		if(x<=M) update(nod<<1,L,M);
		if(M<y) update((nod<<1)+1,M+1,R);

		T[nod].L=T[nod<<1].L;
		if(T[nod].L==M-L+1) T[nod].L+=T[(nod<<1)+1].L;
		T[nod].R=T[(nod<<1)+1].R;
		if(T[nod].R==R-M) T[nod].R+=T[nod<<1].R;

		T[nod].Q=T[nod<<1].Q;
		if(T[nod].Q<T[(nod<<1)+1].Q) T[nod].Q=T[(nod<<1)+1].Q;
		if(T[nod].Q<T[nod<<1].R+T[(nod<<1)+1].L) T[nod].Q=T[nod<<1].R+T[(nod<<1)+1].L;
	}
}

int main()
{
	freopen("hotel.in","r",stdin);
	freopen("hotel.out","w",stdout);

	scanf("%d%d",&N,&P);

	T[1].L=T[1].R=T[1].Q=N;

	for(i=1;i<=P;i++)
	{
		scanf("%d",&c);
		if(c==3) printf("%d\n",T[1].Q);
		else
		{
			scanf("%d%d",&x,&y);
			y+=(x-1);
			update(1,1,N);
		}
	}

	return 0;
}