Cod sursa(job #542590)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 26 februarie 2011 16:27:49
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<stdio.h>
#define maxN 100005
FILE*f=fopen("hotel.in","r");
FILE*g=fopen("hotel.out","w");

int N,M,i,t,a,b,l;

struct arb{
	int Mx;
	int L;
	int R;
}A[4 * maxN];

int max(int a,int b){
	if ( a > b )
		return a;
	return b;
}

void add(int nod,int st,int dr){
	if ( a <= st && dr <= b ){
		A[nod].Mx = A[nod].L = A[nod].R = 0;
		return ;
	}
	
	int mj = ( st + dr ) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	if ( A[nod].Mx == 0 ){
		A[nodst].Mx = A[nodst].L = A[nodst].R = 0;
		A[noddr].Mx = A[noddr].L = A[noddr].R = 0;
	}
	if ( A[nod].Mx == dr - st + 1){
		A[nodst].Mx = A[nodst].L = A[nodst].R = mj - st + 1;
		A[noddr].Mx = A[noddr].L = A[noddr].R = dr - mj;
	}
	
	if ( a <= mj )
		add(nodst,st,mj);
	if ( b > mj )
		add(noddr,mj+1,dr);
	
	A[nod].Mx = max(A[nodst].R + A[noddr].L,max(A[noddr].Mx,A[nodst].Mx));
	if ( A[nodst].L == mj - st + 1 )
		A[nod].L = A[nodst].L + A[noddr].L;
	else
		A[nod].L = A[nodst].L;
	
	if ( A[noddr].R == dr - mj )
		A[nod].R = A[noddr].R + A[nodst].R;
	else
		A[nod].R = A[noddr].R;
	
}

void init(int nod,int st,int dr){
	if ( st == dr ){
		A[nod].L = A[nod].Mx = A[nod].R = 1;
		return ;
	}
	A[nod].L = A[nod].Mx = A[nod].R = dr - st + 1;
	int mj = ( st + dr ) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	init(nodst,st,mj);
	init(noddr,mj+1,dr);
	
}

void del(int nod,int st,int dr){
	if ( a <= st && dr <= b ){
		A[nod].Mx = A[nod].L = A[nod].R = dr - st + 1;
		return ;
	}
	int mj = ( st + dr ) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( A[nod].Mx == 0 ){
		A[nodst].Mx = A[nodst].L = A[nodst].R = 0;
		A[noddr].Mx = A[noddr].L = A[noddr].R = 0;
	}
	if ( A[nod].Mx == dr - st + 1){
		A[nodst].Mx = A[nodst].L = A[nodst].R = mj - st + 1;
		A[noddr].Mx = A[noddr].L = A[noddr].R = dr - mj;
	}
	
	if ( a <= mj )
		del(nodst,st,mj);
	if ( b > mj )
		del(noddr,mj+1,dr);
	
	A[nod].Mx = max(A[nodst].R + A[noddr].L,max(A[noddr].Mx,A[nodst].Mx));
	if ( A[nodst].L == mj - st + 1 )
		A[nod].L = A[nodst].L + A[noddr].L;
	else
		A[nod].L = A[nodst].L;
	
	if ( A[noddr].R == dr - mj )
		A[nod].R = A[noddr].R + A[nodst].R;
	else
		A[nod].R = A[noddr].R;
	
	
}

int main () {
	fscanf(f,"%d %d",&N,&M);
	init(1,1,N);
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d",&t);
		if ( t == 3 ){
			fprintf(g,"%d\n",A[1].Mx);
			continue;
		}
		fscanf(f,"%d %d",&a,&l);
		b = a + l - 1;
		if ( t == 1 ){
			add(1,1,N);
		}
		else{
			del(1,1,N);
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}