Cod sursa(job #541924)

Utilizator Addy.Adrian Draghici Addy. Data 25 februarie 2011 16:20:20
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100050

#define ns (nod << 1)
#define nd ((nod << 1) + 1)
#define mij ((st + dr) >> 1)

struct arb {
	int a, b, c, nr;
} A[4 * NMAX];

int tip, n, m, i, a, b;

void arbore (int, int, int), update (int, int, int, int, int, int);

int main () {
	
	freopen ("hotel.in", "r", stdin);
	freopen ("hotel.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	arbore (1, 1, n);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d", &tip);
		
		if (tip == 1) {
			scanf ("%d %d", &a, &b);
			update (1, 1, n, a, a + b - 1, -1);
		}
		
		if (tip == 2) {
			scanf ("%d %d", &a, &b);
			update (1, 1, n, a, a + b - 1, 1);
		}
		
		if (tip == 3) printf ("%d\n", A[1].c);
	}
	
	return 0;
}

void arbore (int nod, int st, int dr) {
	
	if (st == dr) {
		A[nod].a = A[nod].b = A[nod].c = 1;
		return;
	}
	
	arbore (ns, st, mij);
	arbore (nd, mij + 1, dr);
	
	A[nod].a = A[nod].b = A[nod].c = dr - st + 1;
}

void update (int nod, int st, int dr, int a, int b, int nr) {
	
	if (a <= st && dr <= b) {
		A[nod].nr = nr;
		if (nr == -1) A[nod].a = A[nod].b = A[nod].c = 0;
		if (nr == 1) A[nod].a = A[nod].b = A[nod].c = dr - st + 1;
		return;
	}
	
	if (A[nod].nr) {
		int v = A[nod].nr; A[nod].nr = 0;
		A[ns].nr = v, A[nd].nr = v;
	}
	
	if (a <= mij) update (ns, st, mij, a, b, nr);
	if (mij < b) update (nd, mij + 1, dr, a, b, nr);
	
	if (A[ns].nr == 1 && A[nd].nr == -1) {
		A[nod].a = A[nod].c = mij - st + 1, A[nod].b = 0;
		return;
	}
	
	if (A[ns].nr == -1 && A[nd].nr == 1) {
		A[nod].a = 0, A[nod].b = A[nod].c = dr - mij;
		return;
	}
	
	if (A[ns].nr == -1 && A[nd].nr == -1) {
		A[nod].a = A[nod].b = A[nod].c = 0;
		return;
	}
	
	if (!A[ns].nr) {
		if (A[nd].nr == -1) {
			A[nod].a = A[ns].a, A[nod].b = 0, A[nod].c = A[ns].c;
			return;
		}
		
		if (A[nd].nr == 1) {
			if (A[ns].a == mij - st + 1) A[nod].a = mij - st + 1 + A[nd].a;
			else A[nod].a = A[ns].a;
			
			A[nod].b = A[ns].b + dr - mij, A[nod].c = max (A[ns].c, A[ns].b + dr - mij);
			return;
		}
	}
	
	if (!A[nd].nr) {
		if (A[ns].nr == -1) {
			A[nod].a = 0, A[nod].b = A[nd].b, A[nod].c = A[nd].c;
			return;
		}
		
		if (A[ns].nr == 1) {
			if (A[nd].b == dr - mij) A[nod].b = A[ns].b + dr - mij;
			else A[nod].b = A[nd].b;
			
			A[nod].a = mij - st + 1 + A[nd].a, A[nod].c = max (A[nd].c, mij - st + 1 + A[nd].a);
			return;
		}
	}
	
	if (A[ns].a == mij - st + 1) A[nod].a = mij - st + 1 + A[nd].a;
	else A[nod].a = A[ns].a;
	
	if (A[nd].b == dr - mij) A[nod].b = A[ns].b + dr - mij;
	else A[nod].b = A[nd].b;
	
	A[nod].c = max (max (A[ns].c, A[nd].c), A[ns].b + A[nd].a);
}