Cod sursa(job #495800)

Utilizator ZethpixZethpix Zethpix Data 26 octombrie 2010 21:12:30
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>

struct copac
{
	int max,L,R;
}A[1000002];

int i,n,p,x,y,c;

void update(int nod,int L,int R,int a,int b,int v)
{
	int M;

	if(a<=L&&R<=b)
	{
		if(v==-1)
		{
			A[nod].max=0;
			A[nod].L=0;
			A[nod].R=0;
		}
		else
		{
			A[nod].max=R-L+1;
			A[nod].L=R-L+1;
			A[nod].R=R-L+1;
		}
	}
	else
	{
		M=(L+R)/2;
		if(a<=M) update(2*nod,L,M,a,b,v);
		if(b>M) update(2*nod+1,M+1,R,a,b,v);
		A[nod].L=A[2*nod].L;
		if(A[2*nod].L==A[2*nod].R&&A[2*nod].L!=0) A[nod].L+=A[2*nod+1].L;
		A[nod].R=A[2*nod+1].R;
		if(A[2*nod+1].L==A[2*nod+1].R&&A[2*nod+1].R!=0) A[nod].R+=A[2*nod].R;
		A[nod].max=A[2*nod].L;
		if(A[nod].max<A[2*nod+1].R) A[nod].max=A[2*nod+1].R;
		if(A[nod].max<A[2*nod].R+A[2*nod+1].L) A[nod].max=A[2*nod].R+A[2*nod+1].L;
	}
}

void init(int nod,int L,int R)
{
	int M;

	if(L==R)
	{
		A[nod].max=1;
		A[nod].L=1;
		A[nod].R=1;
	}
	else
	{
		M=(L+R)/2;
		init(2*nod,L,M);
		init(2*nod+1,M+1,R);
		A[nod].max=A[2*nod].max+A[2*nod+1].max;
		A[nod].L=A[2*nod].L+A[2*nod+1].L;
		A[nod].R=A[2*nod].R+A[2*nod+1].R;
	}
}

int main()
{
	freopen("hotel.in","r",stdin);
	freopen("hotel.out","w",stdout);
	scanf("%d%d",&n,&p);

	init(1,1,n);
	for(i=1;i<=p;i++)
	{
		scanf("%d",&c);
		if(c==3) printf("%d\n",A[1].max);
		else
		{
			scanf("%d%d",&x,&y);
			if(c==1) update(1,1,n,x,x+y-1,-1);
			else
			if(c==2) update(1,1,n,x,x+y-1,1);
		}
	}

	return 0;
}