Cod sursa(job #2466956)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 3 octombrie 2019 12:51:56
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>
#define ls (node<<1)
#define rs (ls+1)

using namespace std;

ifstream f("hotel.in");
ofstream g("hotel.out");

const int Nmax=1e5+5;

struct Segment_Tree{

    int lft,rgh,vl,lazy;
};

Segment_Tree Aint[4*Nmax];

void update(int p, int q, int x, int y, int node, int val){

    if(x<=p and q<=y){

        Aint[node].lazy=val;
        if(val==1)
            Aint[node].vl=Aint[node].lft=Aint[node].rgh=q-p+1;
        else
            Aint[node].vl=Aint[node].lft=Aint[node].rgh=0;
    }
    else{

        int mid=(p+q)>>1;
        if(Aint[node].lazy){

            int w=Aint[node].lazy;
            Aint[node].lazy=0;
            update(p,mid,p,mid,ls,w);
            update(mid+1,q,mid+1,q,rs,w);
        }

        if(mid>=x)
            update(p,mid,x,y,ls,val);
        if(mid<y)
            update(mid+1,q,x,y,rs,val);

        Aint[node].vl=max({Aint[ls].vl,Aint[rs].vl,Aint[ls].rgh+Aint[rs].lft});

        Aint[node].lft=Aint[ls].lft;
        Aint[node].rgh=Aint[rs].rgh;

        if(Aint[ls].lft==(mid-p+1))
            Aint[node].lft+=Aint[rs].lft;
        if(Aint[rs].rgh==(q-mid))
            Aint[node].rgh+=Aint[ls].rgh;
    }
}

int main(){

    int n,m,op,lo,hi;
    f>>n>>m;
    for(int i=1;i<=n;i++)
        update(1,n,i,i,1,1);
    while(m--){

        f>>op;
        if(op==1){

            f>>lo>>hi;
            update(1,n,lo,lo+hi-1,1,-1);
        }
        if(op==2){

            f>>lo>>hi;
            update(1,n,lo,lo+hi-1,1,1);
        }
        if(op==3){

            g<<Aint[1].vl<<'\n';
        }
    }

    return 0;
}