Cod sursa(job #1035938)

Utilizator enedumitruene dumitru enedumitru Data 18 noiembrie 2013 21:31:38
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
using namespace std;
ifstream f("hotel.in"); ofstream g("hotel.out");
const int Dmax=300001;
int N,M,A[Dmax],B[Dmax],C[Dmax];
void update(int n, int l, int r, int a, int b, int t)
{	if(a<=l && r<=b)
		if(t==1) A[n]=B[n]=C[n]=0; else A[n]=B[n]=C[n]=r-l+1;
	else
	{	int m=(l+r)>>1;
		if(A[n]==r-l+1) {A[2*n]=B[2*n]=C[2*n]=m-l+1; A[2*n+1]=B[2*n+1]=C[2*n+1]=r-m;}
		if(A[n]==0)	{A[2*n]=B[2*n]=C[2*n]=0; A[2*n+1]=B[2*n+1]=C[2*n+1]=0;}
		if(a<=m) update(2*n,l,m,a,b,t);
		if(m<b) update (2*n+1,m+1,r,a,b,t);
		if(B[2*n]==m-l+1) B[n]=m-l+1+B[2*n+1]; else B[n]=B[2*n];
		if(C[2*n+1]==r-m) C[n]=r-m+C[2*n]; else C[n]=C[2*n+1];
		A[n]= A[2*n]>A[2*n+1] ? A[2*n] : A[2*n+1];
		if(A[n]<B[2*n+1]+C[2*n]) A[n]=B[2*n+1]+C[2*n];
	}
}
int main()
{	f>>N>>M;
	A[1]=B[1]=C[1]=N;
	while(M--)
	{	int t,a,b;
		f>>t;
		if(t<3) f>>a>>b, update(1,1,N,a,a+b-1,t); else g<<A[1]<<"\n";
	}
	g.close(); return 0;
}