Cod sursa(job #551693)

Utilizator lacalutlacalut lacalut Data 10 martie 2011 23:26:36
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <algorithm>
#include <stdio.h>

#define MAX 100010

using namespace std;

int n, q;
int totAInt[4 * MAX], stAInt[4 * MAX], drAInt[4 * MAX], upd[4 * MAX];

inline void addAInt(int nod, int fr, int ls, int st, int dr, int key)
{
	if (st <= fr && ls <= dr)
	{
		upd[nod] = key;

		totAInt[nod] = stAInt[nod] = drAInt[nod] = key * (ls - fr + 1);

		return;
	}

	int med = (fr + ls) / 2;

	if (upd[nod] != -1)
	{
		addAInt(nod * 2, fr, med, fr, med, upd[nod]);
		addAInt(nod * 2 + 1, med + 1, ls, med + 1, ls, upd[nod]);

		upd[nod] = -1;
	}

	if (st <= med)
		addAInt(nod * 2, fr, med, st, dr, key);
	if (med < dr)
		addAInt(nod * 2 + 1, med + 1, ls, st, dr, key);

	totAInt[nod] = max(drAInt[nod * 2] + stAInt[nod * 2 + 1], max(totAInt[nod * 2], totAInt[nod * 2 + 1]));
	if (totAInt[nod * 2] == med - fr + 1)
		stAInt[nod] = totAInt[nod * 2] + stAInt[nod * 2 + 1];
	else stAInt[nod] = stAInt[nod * 2];
	if (totAInt[nod * 2 + 1] == ls - med)
		drAInt[nod] = totAInt[nod * 2 + 1] + drAInt[nod * 2];
	else drAInt[nod] = drAInt[nod * 2 + 1];
}

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

	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
		upd[i] = -1;
	addAInt(1, 1, n, 1, n, 1);

	for (; q; q--)
	{
		int caz;
		scanf("%d", &caz);

		if (caz == 1)
		{
			int x, y;
			scanf("%d %d", &x, &y);

			addAInt(1, 1, n, x, x + y - 1, 0);
		}
		else if (caz == 2)
		{
			int x, y;
			scanf("%d %d", &x, &y);

			addAInt(1, 1, n, x, x + y - 1, 1);
		}
		else printf("%d\n", totAInt[1]);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}