Cod sursa(job #469969)

Utilizator ilincaSorescu Ilinca ilinca Data 10 iulie 2010 01:23:04
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>

#define nmax 100005
#define W 300005

struct arbint
{
	int m, l, r, v;
	bool ok;
};

int n, a, b, V;
arbint arb [W];

inline int max (int a, int b)
{return (a > b)? a:b;}

inline void mod (arbint &nod,  int lg, int v)
{
	nod.v=v;
	nod.ok=true;
	if (v == 0)
		nod.m=nod.l=nod.r=lg;
	else
		nod.m=nod.l=nod.r=0;
}

void init (int k, int l, int r)
{
	mod (arb [k], r-l+1, 0);
	arb [k].ok=false;
	if (l == r) return;
	int m=(l+r)>>1;
	init (k<<1, l, m);
	init ((k<<1) + 1, m+1, r);
}

void update (int k, int l, int r)
{

	int mij=(l+r)>>1;
	if (arb [k].ok == true && l != r)
	{
		mod (arb [k<<1], mij-l+1, arb [k].v);
		mod (arb [(k<<1)+1], r-mij, arb [k].v);
		arb [k].ok=false;
	}
	
	if (l >= a && r <= b)
	{
		mod (arb [k], r-l+1, V);
		return;
	}


	if (a <= mij) update (k<<1, l, mij);
	if (b > mij) update ((k<<1)+1, mij+1, r);

	arb [k].l=arb [k<<1].l;
	if (arb [k<<1].l == mij-l+1) arb [k].l += arb [(k<<1)+1].l;
	arb [k].r=arb [(k<<1)+1].r;
	if (arb [(k<<1)+1].r == r-mij) arb [k].r += arb [k<<1].r;
	
	arb [k].m=max (arb [k].l, arb [k].r);
	arb [k].m=max (arb [k].m, arb [k<<1].m);
	arb [k].m=max (arb [k].m, arb [(k<<1)+1].m);
	arb [k].m=max (arb [k].m, arb [k<<1].r + arb [(k<<1)+1].l);
}

int main ()
{
	freopen ("hotel.in", "r", stdin);	
	freopen ("hotel.out", "w", stdout);
	int p, tip;
	scanf ("%d%d", &n, &p);
	init (1, 1, n);
	for (; p; --p)
	{
		scanf ("%d", &tip);
		if (tip == 3)
		{
			printf ("%d\n", arb [1].m);
			continue;
		}
		scanf ("%d%d", &a, &b);
		b += a-1;
		if (tip == 1)
			V=1;
		else
			V=0;
		update (1, 1, n);
	}
	return 0;
}