Cod sursa(job #2393552)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 31 martie 2019 17:43:49
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <iostream>
#include <cstdio>

#define N 100005

using namespace std;

struct Nod{
    int val, prefix, sufix;
    Nod(){
        ;
    }
    Nod(int lval){
        val=prefix=sufix=lval;
    }
}arbint[4*N];
int l[4*N];

int n,p,c,x,y;

void construieste(int st = 1, int dr = n, int pos = 1){
    if(st==dr){
        arbint[pos]=Nod(1);
        return;
    }
    int mij = (st+dr)/2;
    construieste(st,mij,2*pos);
    construieste(mij+1,dr,2*pos+1);
    arbint[pos].prefix=arbint[pos].sufix=arbint[pos].val=dr-st+1;
}

void actualizareFii(int st, int dr, int pos){
    if(l[pos]==0)
        return ;
    int mij = (st+dr)/2;
    if(l[pos]==-1){
        arbint[2*pos]=Nod(mij-st+1);
        arbint[2*pos+1]=Nod(dr-mij);
    }
    else{
        arbint[2*pos]=Nod(0);
        arbint[2*pos+1]=Nod(0);
    }
    l[2*pos]=l[2*pos+1]=l[pos];
    l[pos]=0;
}

void actualizareNod(int st, int dr, int pos){
    int mij = (st+dr)/2;

    arbint[pos].val=max(arbint[2*pos].val,max(
                    arbint[2*pos+1].val,
                    arbint[2*pos].sufix+arbint[2*pos+1].prefix));

    arbint[pos].prefix=arbint[2*pos].prefix;
    arbint[pos].sufix=arbint[2*pos+1].sufix;

    if(arbint[pos].sufix==dr-mij)
        arbint[pos].sufix+=arbint[2*pos].sufix;

    if(arbint[pos].prefix==mij-st+1)
        arbint[pos].prefix+=arbint[2*pos+1].prefix;
}

void actualizareInterval(int val, int qst, int qdr, int st=1, int dr = n, int pos = 1){
    if(qdr<st || qst>dr)
        return ;
    if(qst<=st && dr<=qdr){
        if(val>0)
            arbint[pos]=Nod(0);
        else
            arbint[pos]=Nod(dr-st+1);
        l[pos]=val;
        return ;
    }
    int mij = (st+dr)/2;
    actualizareFii(st,dr,pos);
    actualizareInterval(val,qst,qdr,st,mij,2*pos);
    actualizareInterval(val,qst,qdr,mij+1,dr,2*pos+1);

    actualizareNod(st,dr,pos);
}

int main()
{
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);

    scanf("%d%d",&n,&p);
    construieste();
    for(int i=0;i<p;++i){
        scanf("%d", &c);
        if(c<3){
            scanf("%d%d",&x,&y);
            if(c==1)
                actualizareInterval(+1,x,x+y-1);
            else
                actualizareInterval(-1,x,x+y-1);
        }
        else
            cout<<arbint[1].val<<'\n';
    }
    return 0;
}