Cod sursa(job #770447)

Utilizator vlad.maneaVlad Manea vlad.manea Data 23 iulie 2012 00:32:50
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <cstdio>
#define INFILE "hotel.in"
#define OUTFILE "hotel.out"
#define NLOGN 2500000

using namespace std;
int N, P;

int Left[NLOGN], Right[NLOGN], Total[NLOGN];

inline int Max(int left, int right)
{
	return left > right? left: right;
}

void Insert(int node, int maxLeft, int maxRight, int left, int right)
{
	if (left <= maxLeft && maxRight <= right)
	{
		Total[node] = Left[node] = Right[node] = 0;
		return;
	}

	int middle = (maxLeft + maxRight) >> 1;
	int leftNode = node << 1;
	int rightNode = node << 1 | 1;

	if (Total[node] == maxRight - maxLeft + 1)
	{
		Left[leftNode] = Right[leftNode] = Total[leftNode] = middle - maxLeft + 1;
		Left[rightNode] = Right[rightNode] = Total[rightNode] = maxRight - middle;
	}

	if (left <= middle)
	{
		Insert(leftNode, maxLeft, middle, left, right);
	}

	if (right > middle)
	{
		Insert(rightNode, middle + 1, maxRight, left, right);
	}

	Left[node] = Max(Left[leftNode], Total[leftNode] == middle - maxLeft + 1? Total[leftNode] + Left[rightNode]: 0);
	Right[node] = Max(Right[rightNode], Total[rightNode] == maxRight - middle? Total[rightNode] + Right[leftNode]: 0);
	
	Total[node] = Max(Total[leftNode], Total[rightNode]);
	Total[node] = Max(Total[node], Right[leftNode] + Left[rightNode]);
}

void Delete(int node, int maxLeft, int maxRight, int left, int right)
{
	if (left <= maxLeft && maxRight <= right)
	{
		Total[node] = Left[node] = Right[node] = right - left + 1;
		return;
	}

	int middle = (maxLeft + maxRight) >> 1;
	int leftNode = node << 1;
	int rightNode = node << 1 | 1;

	if (Total[node] == 0)
	{
		Left[leftNode] = Right[leftNode] = Total[leftNode] = 0;
		Left[rightNode] = Right[rightNode] = Total[rightNode] = 0;
	}

	if (left <= middle)
	{
		Delete(leftNode, maxLeft, middle, left, right);
	}

	if (right > middle)
	{
		Delete(rightNode, middle + 1, maxRight, left, right);
	}

	Left[node] = Max(Left[leftNode], Total[leftNode] == middle - maxLeft + 1? Total[leftNode] + Left[rightNode]: 0);
	Right[node] = Max(Right[rightNode], Total[rightNode] == maxRight - middle? Total[rightNode] + Right[leftNode]: 0);
	
	Total[node] = Max(Total[leftNode], Total[rightNode]);
	Total[node] = Max(Total[node], Right[leftNode] + Left[rightNode]);
}

void Initialize(int node, int left, int right)
{
	Total[node] = Left[node] = Right[node] = right - left + 1;

	if (left >= right)
	{
		return;
	}

	int middle = (left + right) >> 1;
	int leftNode = node << 1;
	int rightNode = node << 1 | 1;

	Initialize(leftNode, left, middle);
	Initialize(rightNode, middle + 1, right);
}

int main()
{
	int c, i, M;

	freopen(INFILE, "r", stdin);
	freopen(OUTFILE, "w", stdout);

	scanf("%d%d", &N, &P);
	Initialize(1, 1, N);

	while (P--)
	{
		scanf("%d", &c);

		switch(c)
		{
			case 1:
			{
				scanf("%d%d", &i, &M);
				Insert(1, 1, N, i, i + M - 1);
				break;
			}
		
			case 2:
			{
				scanf("%d%d", &i, &M);
				Delete(1, 1, N, i, i + M - 1);
				break;
			}

			case 3:
			{
				printf("%d\n", Total[1]);
				break;
			}
		}
	}

	return 0;
}