Cod sursa(job #1737837)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 4 august 2016 23:57:55
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <algorithm>
#define MAX 65536
#define MaxN 200001
using namespace std;
 
int p=0,N,P,V1,V2,Type,sign,X;
char f[MAX];
int MX(int a,int b,int c)
{
	X=max(a,b);
	X=max(X,c);
	return X;
}
struct Tree
{
	int R,L,Start,End,All;
}v[MaxN];
void r(int &nr)
{
	nr=0;
	sign=0;
	while(f[p]<'0'||f[p]>'9')
	{
		if(f[p]=='-')
			sign=1;
        p++;
        if(p==MAX)
            fread(f,1,MAX,stdin),p=0;
     }
    while(f[p]>='0'&&f[p]<='9')
    {
        nr=nr*10+f[p++]-'0';
        if(p==MAX)
            fread(f,1,MAX,stdin),p=0;
    }
    if(sign==1)
        nr=-nr;
}
void CreateNode(int pos,int L,int R)
{
	v[pos].L=L;v[pos].R=R;
	v[pos].Start=R-L+1;
	v[pos].End=R-L+1;
	v[pos].All=R-L+1;
	if(L<R)
	{
		int mid=(L+R)>>1;
		CreateNode(2*pos,L,mid);
		CreateNode(2*pos+1,mid+1,R);
	}
}
void Answer()
{
	printf("%d\n",v[1].All);
}
void Add(int A,int B,int pos,int mid)
{
	if(v[pos].L>=A&&v[pos].R<=B)
		v[pos].All=v[pos].End=v[pos].Start=0;
	if(v[pos].L<v[pos].R)
		mid=(v[pos].R+v[pos].L)>>1;
	else return;
	if(mid>=A)
		Add(A,B,2*pos,1);
	if(mid<B)
		Add(A,B,2*pos+1,1);
	v[pos].All=MX(v[pos*2].All,v[2*pos+1].All,v[pos*2].End+v[pos*2+1].Start);
	v[pos].Start=v[pos*2].Start+(v[pos*2].Start==v[2*pos].R-v[2*pos].L+1)*v[pos*2+1].Start;
	v[pos].End=v[pos*2+1].End+(v[pos*2+1].End==v[2*pos+1].R-v[2*pos+1].L+1)*v[pos*2].End;
}
void Remove(int A,int B,int pos,int mid)
{
	if(v[pos].L>=A&&v[pos].R<=B)
		v[pos].All=v[pos].End=v[pos].Start=v[pos].R-v[pos].L+1;
	if(v[pos].L<v[pos].R)
		mid=(v[pos].R+v[pos].L)>>1;
	else return;
	if(mid>=A)
		Remove(A,B,2*pos,1);
	if(mid<B)
		Remove(A,B,2*pos+1,1);
	v[pos].All=MX(v[pos*2].All,v[2*pos+1].All,v[pos*2].End+v[pos*2+1].Start);
	v[pos].Start=v[pos*2].Start+(v[pos*2].Start==v[2*pos].R-v[2*pos].L+1)*v[pos*2+1].Start;
	v[pos].End=v[pos*2+1].End+(v[pos*2+1].End==v[2*pos+1].R-v[2*pos+1].L+1)*v[pos*2].End;
}
int main()
{
	freopen("hotel.in","r",stdin);
	freopen("hotel.out","w",stdout);
	fread(f,1,MAX,stdin);
	r(N);r(P);
	CreateNode(1,1,N);
	for(int i=1;i<=P;i++)
	{
		r(Type);
		if(Type==3)
			Answer();
		else if(Type==1)
		{
			r(V1);r(V2);
			Add(V1,V1+V2-1,1,1);
		}
		else if(Type==2)
		{
			r(V1);r(V2);
			Remove(V1,V1+V2-1,1,1);
		}
	}
	return 0;
}