Cod sursa(job #2466243)

Utilizator mihaimodiMihai Modi mihaimodi Data 1 octombrie 2019 19:33:12
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");

struct arb
{
    int lazy;
    int st,dr,val;
}aint[300000];
int n,m,t;
void update(int nod, int st, int dr, int x, int y, int val)
{
    if(st>dr)
        return;
    int mid=(st+dr)/2;
    if(st>=x&&dr<=y)
    {
        aint[nod].st+=val*(dr-st+1);
        aint[nod].dr+=val*(dr-st+1);
        aint[nod].lazy=val;
        aint[nod].val+=val*(dr-st+1);
        return;
    }
    if(aint[nod].lazy!=0)
    {
        update(2*nod,st,mid,st,mid,aint[nod].lazy);
        update(2*nod+1,mid+1,dr,mid+1,dr,aint[nod].lazy);
        aint[nod].lazy=0;
    }
    if(x<=mid)
        update(2*nod,st,mid,x,y,val);
    if(y>mid)
        update(2*nod+1,mid+1,dr,x,y,val);
    aint[nod].val=max(aint[2*nod].val,aint[2*nod+1].val);
    aint[nod].val=max(aint[nod].val,aint[2*nod].dr+aint[2*nod+1].st);
    aint[nod].st=aint[2*nod].st;
    if(aint[2*nod].val==(mid-st+1))
        aint[nod].st+=aint[2*nod+1].st;
    aint[nod].dr=aint[2*nod+1].dr;
    if(aint[2*nod+1].val==(dr-mid))
        aint[nod].dr+=aint[2*nod].dr;
}
int main ()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        update(1,1,n,i,i,1);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        fin>>t;
        if(t==1)
        {
            fin>>x>>y;
            update(1,1,n,x,x+y-1,-1);
        }
        else if(t==2)
        {
            fin>>x>>y;
            update(1,1,n,x,x+y-1,1);
        }
        else if(t==3)
            fout<<aint[1].val<<'\n';
    }

    return 0;
}