Cod sursa(job #540891)

Utilizator ChallengeMurtaza Alexandru Challenge Data 24 februarie 2011 16:00:18
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>

using namespace std;

const char InFile[]="hotel.in";
const char OutFile[]="hotel.out";
const int aint_SIZE=1<<18;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_aint_node
{
	int A,R,L,S,AUX;
};

int N,M,op,a,b;
s_aint_node aint[aint_SIZE];

int update_st,update_dr,update_val;
int query_result,query_prefix,query_st,query_dr;

inline int father(const int &nod)
{
	return nod>>1;
}

inline int left(const int &nod)
{
	return nod<<1;
}

inline int right(const int &nod)
{
	return (nod<<1)|1;
}

inline void update_aux(int st, int dr, int nod)
{
	int l=left(nod);
	int r=right(nod);
	if(st<dr)
	{
		aint[l].AUX+=aint[nod].AUX;
		aint[r].AUX+=aint[nod].AUX;
	}
	if(aint[nod].AUX==1)
	{
		aint[nod].L=aint[nod].R=aint[nod].S=aint[nod].A=dr-st+1;
	}
	else if(aint[nod].AUX==-1)
	{
		aint[nod].L=aint[nod].R=aint[nod].S=aint[nod].A=0;
	}
	aint[nod].AUX=0;
}

void update_aint(int st, int dr, int nod)
{
	if(update_st<=st && dr<=update_dr)
	{
		aint[nod].AUX+=update_val;
		update_aux(st,dr,nod);
		return;
	}
	update_aux(st,dr,nod);
	int l=left(nod);
	int r=right(nod);
	int m=st+((dr-st)>>1);
	update_aux(st,m,l);
	update_aux(m+1,dr,r);
	if(update_st<=m)
	{
		update_aint(st,m,l);
	}
	if(update_dr>m)
	{
		update_aint(m+1,dr,r);
	}

	if(aint[l].S!=0 && aint[r].S!=0)
	{
		aint[nod].S=dr-st+1;
	}
	else
	{
		aint[nod].S=0;
	}
	if(aint[l].S!=0)
	{
		aint[nod].L=aint[l].S+aint[r].L;
	}
	else
	{
		aint[nod].L=aint[l].L;
	}
	if(aint[r].S!=0)
	{
		aint[nod].R=aint[r].S+aint[l].R;
	}
	else
	{
		aint[nod].R=aint[r].R;
	}
	aint[nod].A=max(max(aint[l].A,aint[r].A),aint[l].R+aint[r].L);
}

inline void update(const int &st, const int &dr, const int &val)
{
	update_st=st;
	update_dr=dr;
	update_val=val;
	update_aint(1,N,1);
}

void query_aint(int st, int dr, int nod)
{
	query_result=aint[nod].A;
}

inline int query(const int &st, const int &dr)
{
	query_result=query_prefix=0;
	query_st=st;
	query_dr=dr;
	query_aint(1,N,1);
	return query_result;
}

int main()
{
	fin>>N>>M;
	update(1,N,1);
	for(register int i=1;i<=M;++i)
	{
		fin>>op;
		if(op!=3)
		{
			fin>>a>>b;
			if(op==1)
			{
				update(a,a+b-1,-1);
			}
			else
			{
				update(a,a+b-1,1);
			}
		}
		else
		{
			fout<<query(1,N)<<"\n";
		}
	}
	fin.close();
	fout.close();
	return 0;
}