Cod sursa(job #322422)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 8 iunie 2009 20:02:38
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <cstring>
#define FIN "hotel.in"
#define FOUT "hotel.out"
#define MAXN 100010
using namespace std;
struct node { int stanga,dreapta,maxim,lazy;} Ai[4*MAXN];
int N,P;


void iofile(void){

		freopen(FIN,"rt",stdin);
		freopen(FOUT,"wt",stdout);

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

		return ;
}

void update(int nod,int p,int u,int a,int b,int c){

		if (a<=p && u<=b){

				if (c){

				Ai[nod].lazy=1;
				Ai[nod].maxim=0;
				Ai[nod].stanga=0;
				Ai[nod].dreapta=0;
				} else {
						Ai[nod].lazy=0;
						Ai[nod].maxim=u-p+1;
						Ai[nod].stanga=u-p+1;
						Ai[nod].dreapta=u-p+1;
				}
		} else {

				int m=(p+u)/2;
				if (!c && Ai[nod].lazy){ //daca e de sters, facem split

						Ai[nod].lazy=0;
						Ai[nod*2].lazy=1;
						Ai[nod*2].maxim=0;
						Ai[nod*2].stanga=0;
						Ai[nod*2].dreapta=0;

						Ai[nod*2+1].lazy=1;
						Ai[nod*2+1].maxim=0;
						Ai[nod*2+1].stanga=0;
						Ai[nod*2+1].dreapta=0;
				}

				if (a<=m) update(nod*2,p,m,a,b,c);
				if (b>m)  update(nod*2+1,m+1,u,a,b,c);

				//refac maximele ...

				Ai[nod].stanga=Ai[nod*2].stanga;
				if (Ai[nod*2].stanga==m-p+1){
						Ai[nod].stanga+=Ai[nod*2+1].stanga;
				}

				Ai[nod].dreapta=Ai[nod*2+1].dreapta;
				if (Ai[nod*2+1].dreapta==u-m){
						Ai[nod].dreapta+=Ai[nod*2].dreapta;
				}

				Ai[nod].maxim=max(Ai[nod*2].maxim,Ai[nod*2+1].maxim);

				Ai[nod].maxim=max(Ai[nod].maxim,Ai[nod].stanga);
				Ai[nod].maxim=max(Ai[nod].maxim,Ai[nod].dreapta);

				Ai[nod].maxim=max(Ai[nod].maxim,Ai[nod*2].dreapta+Ai[nod*2+1].stanga);

		}
}

void init(int nod,int p,int u){

		if (p==u){

				Ai[nod].maxim=u-p+1;
				Ai[nod].lazy=0;
				Ai[nod].stanga=u-p+1;
				Ai[nod].dreapta=u-p+1;
				return ;
		} else {

				int m=(p+u)/2;
				init(nod*2,p,m);
				init(nod*2+1,m+1,u);
				Ai[nod].stanga=u-p+1;
				Ai[nod].dreapta=u-p+1;
				Ai[nod].maxim=u-p+1;
				Ai[nod].lazy=0;
		}
}


void solve(void){


		int op,M,nr;

		init(1,1,N);

		for (int i=1;i<=P;++i){

				scanf("%d",&op);

				if (op==3){

						printf("%d\n",Ai[1].maxim);
				} else {

						scanf("%d%d",&nr,&M);
						if (op==1) update(1,1,N,nr,nr+M-1,1);
						if (op==2) update(1,1,N,nr,nr+M-1,0);
				}
		}

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

int main(void){

		iofile();
		solve();

		return 0;
}