Cod sursa(job #568129)

Utilizator avram_florinavram florin constantin avram_florin Data 30 martie 2011 20:35:43
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<cstdio>

using namespace std;

const int MaxArb = 1 << 18;
#define max(a, b) ((a)>(b)?(a):(b))

int n,P,st,dr,op;
struct arbore{
		int r,l,c; // rezistor bobina condensator :))
		};
arbore Arb[MaxArb];

void update_initial(int nod , int left , int right )
{
	if( left == right )
		{
			Arb[nod].r = Arb[nod].l = Arb[nod].c = 1;
			return ;
		}
	int midd = (left + right) >> 1;
	update_initial(2*nod, left , midd );
	update_initial(2*nod+1 , midd+1 , right );
	Arb[nod].r = Arb[2*nod].r + Arb[2*nod+1].r;
	Arb[nod].l = Arb[2*nod].l + Arb[2*nod+1].l;
	Arb[nod].c = Arb[2*nod].c + Arb[2*nod+1].c;
}

void update(int nod , int left , int right )
{
	if( st <= left && right <= dr )
		{
			if( op == 1 )
				Arb[nod].l = Arb[nod].c = Arb[nod].r = 0;
				else
				Arb[nod].l = Arb[nod].c = Arb[nod].r = right - left + 1; 
			return;
		}
	if( left >= right )
		return ;
	int midd = (left + right) >> 1;
	if( Arb[nod].c == 0 )
		{
			Arb[2*nod].c = Arb[2*nod].l = Arb[2*nod].r = 0;
			Arb[2*nod+1].c = Arb[2*nod+1].l = Arb[2*nod+1].r = 0;
		}
	if( Arb[nod].c == right - left + 1 )
		{
			Arb[2*nod].c = Arb[2*nod].l = Arb[2*nod].r = midd - left+1;
			Arb[2*nod+1].c = Arb[2*nod+1].l = Arb[2*nod+1].r = right - midd;
		}
	if( st <= midd )
		update(2*nod , left , midd );
	if( midd < dr )
		update(2*nod+1 , midd+1 , right );
	Arb[nod].l = Arb[2*nod].l;
	if( Arb[nod].l == midd - left + 1 )
		Arb[nod].l += Arb[2*nod+1].l;
	Arb[nod].r = Arb[2*nod+1].r;
	if( Arb[nod].r == right - midd )
		Arb[nod].r += Arb[2*nod].r;
	Arb[nod].c = max( max(Arb[2*nod].c , Arb[2*nod+1].c) , Arb[2*nod].r + Arb[2*nod+1].l );
}

int main()
{
	freopen( "hotel.in" , "r" , stdin );
	freopen( "hotel.out" , "w" ,stdout );
	scanf("%d%d" , &n , &P);
	update_initial(1,1,n);
	for( ; P ; P-- )
		{
			scanf("%d" , &op );
			if( op == 1 || op == 2 )
				{
					scanf("%d%d" , &st , &dr );
					dr += (st - 1);
					update(1,1,n);
				}
				else
				printf("%d\n" , Arb[1].c);
		}
	return 0;
}