Cod sursa(job #2489165)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 7 noiembrie 2019 22:52:36
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fi("hotel.in");
ofstream fo("hotel.out");
const int NMAX=1e5+5;
struct node{
	int val, lazy, left, right, maxim;
};
node arb[4*NMAX];
int n,p,caz,x,m;
void propagate(int nod,int st,int dr)
{
	if(!arb[nod].lazy) return;
    arb[nod].val+=arb[nod].lazy*(dr-st+1);
    arb[nod].left=arb[nod].right=arb[nod].maxim=(dr-st+1)-arb[nod].val;
	if(st!=dr)
	{
		arb[2*nod].lazy+=arb[nod].lazy;
		arb[2*nod+1].lazy+=arb[nod].lazy;
	}
	arb[nod].lazy=0;
}
void update(int nod,int st,int dr,int x,int y,int z)
{
    propagate(nod,st,dr);
	if(x>dr || y<st) return ;
	if(st==dr)
	{
		arb[nod].val+=z;
		arb[nod].left=arb[nod].right=arb[nod].maxim=1-arb[nod].val;
		return ;
	}
	if(x<=st && dr<=y)
	{
		arb[nod].val+=z*(dr-st+1);
		arb[2*nod].lazy+=z;
		arb[2*nod+1].lazy+=z;
		arb[nod].left=arb[nod].right=arb[nod].maxim=(dr-st+1)-arb[nod].val;
		return;
	}
	int mij=(st+dr)/2;
	update(2*nod,st,mij,x,y,z);
	update(2*nod+1,mij+1,dr,x,y,z);
	arb[nod].val=arb[2*nod].val+arb[2*nod+1].val;
	if(arb[2*nod].left==mij-st+1)
		arb[nod].left=mij-st+1+arb[2*nod+1].left;
	else arb[nod].left=arb[2*nod].left;
	if(arb[2*nod+1].right==dr-mij)
		arb[nod].right=dr-mij+arb[2*nod].right;
	else arb[nod].right=arb[2*nod+1].right;
	arb[nod].maxim=max(arb[2*nod].right+arb[2*nod+1].left,max(arb[2*nod].maxim,arb[2*nod+1].maxim));
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        arb[nod].left=arb[nod].right=arb[nod].maxim=1;
        return ;
    }
    int mij=(st+dr)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);
    arb[nod].left=arb[nod].right=arb[nod].maxim=dr-st+1;
}
int main()
{
	fi>>n>>p;
	build(1,1,n);
	for(int i=1;i<=p;i++)
	{
		fi>>caz;
		if(caz==1)
		{
			fi>>x>>m;
			update(1,1,n,x,x+m-1,1);
		}
		if(caz==2)
		{
			fi>>x>>m;
			update(1,1,n,x,x+m-1,-1);
		}
		if(caz==3)
		{
			propagate(1,1,n);
			fo<<arb[1].maxim<<"\n";
		}
	}
	fi.close();
	fo.close();
	return 0;
}