Cod sursa(job #2393513)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 31 martie 2019 16:26:51
Problema Hotel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <cstdio>

#define N 100005

using namespace std;

struct Nod{
    int val, prefix, sufix;
}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]={1,1,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 actualizareInterval(int val, int qst, int qdr, int st=1, int dr = n, int pos = 1){
    if(l[pos]){
        if(l[pos]>0)
            arbint[pos]={0,0,0};
        else
            arbint[pos].prefix=arbint[pos].sufix=arbint[pos].val=dr-st+1;
        l[2*pos]+=l[pos];
        l[2*pos+1]+=l[pos];
        l[pos]=0;
    }
    if(qdr<st || qst>dr)
        return ;
    if(qst<=st && dr<=qdr){
        if(val>0)
            arbint[pos]={0,0,0};
        else
            arbint[pos].prefix=arbint[pos].sufix=arbint[pos].val=dr-st+1;
        l[2*pos]+=val;
        l[2*pos+1]+=val;
        return ;
    }
    int mij = (st+dr)/2;
    actualizareInterval(val,qst,qdr,st,mij,2*pos);
    actualizareInterval(val,qst,qdr,mij+1,dr,2*pos+1);

    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].sufix=arbint[2*pos+1].sufix;
    if(arbint[pos].sufix && arbint[2*pos+1].sufix==arbint[2*pos+1].prefix)
        arbint[pos].sufix+=arbint[2*pos].sufix;

    arbint[pos].prefix=arbint[2*pos].prefix;
    if(arbint[pos].prefix && arbint[2*pos].sufix==arbint[2*pos].prefix)
        arbint[pos].prefix+=arbint[2*pos+1].prefix;
}

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;
}