Cod sursa(job #9007)

Utilizator IgnitionMihai Moraru Ignition Data 26 ianuarie 2007 11:38:24
Problema Hotel Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>

//#define MAX(a, b) (a > b? a : b)
#define MN (100009)

inline int max(int x, int y)
{
	return x > y? x : y;
}

int _data[262144][3]; // _data[i][0] = total, [1] = left, [2] = right
// marimea e buna? 262145?

/*
int query(int n, int left, int right, int a, int b)
{
	if(a <= left && right <= b)
		return _data[n][0];
	return 0;
}
*/

void update(int n, int left, int right, int a, int b, int t) // t: 0 = liber, 1 = ocupat
{
	if(a <= left && right <= b)
		_data[n][0] = _data[n][1] = _data[n][2] = (t? 0 : right-left+1);
	if(left >= right)
		return;
	int middle = (left+right)/2;
	if(a <= middle)
		update(2*n, left, middle, a, b, t);
	if(middle < b)
		update(2*n+1, middle+1, right, a, b, t);

	_data[n][1] = _data[2*n][1]+(left+_data[2*n][1]-1 == middle? _data[2*n+1][1] : 0);
	_data[n][2] = _data[2*n+1][2]+(right-_data[2*n+1][2] == middle? _data[2*n][2] : 0);
	_data[n][0] = max(_data[2*n][0], _data[2*n+1][0]);
	_data[n][0] = max(_data[n][0], _data[n][1]);
	_data[n][0] = max(_data[n][0], _data[n][2]);
	_data[n][0] = max(_data[n][0], _data[2*n][2]+_data[2*n+1][1]);
}

int main()
{
	freopen("hotel.in", "r", stdin);
	freopen("hotel.out", "w", stdout);
	
	int N, P;
	
	scanf("%d %d", &N, &P);
	update(1, 1, N, 1, N, 0);
	for(; P --; ) {
		int t, a, b;
		//printf("%d\n", P);
		scanf("%d", &t);
		if(t < 3) {
			scanf("%d %d", &a, &b);
			update(1, 1, N, a, a+b-1, t == 1? 1 : 0);
		} else printf("%d\n", _data[1][0]);
	}

	return 0;
}