Cod sursa(job #3334628)

Utilizator mariusharabariMarius Harabari mariusharabari Data 18 ianuarie 2026 18:30:35
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");

const int NMAX = 1e5+1, AMAX = 4e5+1;

struct ceva{
    int a, b, c;
} aint[AMAX];
int n, p, lazy[AMAX];

void construire(int nod, int l, int r){
    if(l==r)
        aint[nod].a=aint[nod].b=aint[nod].c=1;
    else{
        int m=(l+r)/2;
        construire(2*nod, l, m);
        construire(2*nod+1, m+1, r);

        if(aint[2*nod].a==m-l+1)
            aint[nod].a=aint[2*nod].a+aint[2*nod+1].a;
        else
            aint[nod].a=aint[2*nod].a;

        if(aint[2*nod+1].b==r-m)
            aint[nod].b=aint[2*nod].b+aint[2*nod+1].b;
        else
            aint[nod].b=aint[2*nod+1].b;

        aint[nod].c=max(max(aint[2*nod].c, aint[2*nod+1].c), aint[2*nod].b+aint[2*nod+1].a);
    }
    /*cout<<nod<<' '<<l<<' '<<r<<endl;
    cout<<aint[nod].a<<' '<<aint[nod].b<<' '<<aint[nod].c<<endl<<endl;*/
}

void push(int nod, int l, int r){
    if(l!=r){
        int m=(l+r)/2;
        if(lazy[nod]==-1){
            aint[2*nod].a=aint[2*nod].b=aint[2*nod].c=0;
            aint[2*nod+1].a=aint[2*nod+1].b=aint[2*nod+1].c=0;
            lazy[2*nod]--;
            lazy[2*nod+1]--;
        }
        if(lazy[nod]==1){
            aint[2*nod].a=aint[2*nod].b=aint[2*nod].c=m-l+1;
            aint[2*nod+1].a=aint[2*nod+1].b=aint[2*nod+1].c=r-m;
            lazy[2*nod]++;
            lazy[2*nod+1]++;
        }
    }
    /*if(lazy[nod]==-1){
        aint[nod].a=aint[nod].b=aint[nod].c=0;
        lazy[2*nod]--;
        lazy[2*nod+1]--;
    }
    if(lazy[nod]==1){
        aint[nod].a=aint[nod].b=aint[nod].c=r-l+1;
        lazy[2*nod]++;
        lazy[2*nod+1]++;
    }*/
    lazy[nod]=0;
}

void update(int nod, int al, int ar, int l, int r, int val){
    if(l<=al&&ar<=r){
        lazy[nod]+=val;
        if(val==-1)
            aint[nod].a=aint[nod].b=aint[nod].c=0;
        if(val==1)
            aint[nod].a=aint[nod].b=aint[nod].c=ar-al+1;
    }
    else{
        int m=(al+ar)/2;
        push(nod, al, ar);
        if(m>=l)
            update(2*nod, al, m, l, r, val);
        if(m<r)
            update(2*nod+1, m+1, ar, l, r, val);



        if(aint[2*nod].a==m-al+1)
            aint[nod].a=aint[2*nod].a+aint[2*nod+1].a;
        else
            aint[nod].a=aint[2*nod].a;

        if(aint[2*nod+1].b==ar-m)
            aint[nod].b=aint[2*nod].b+aint[2*nod+1].b;

        else
            aint[nod].b=aint[2*nod+1].b;

        aint[nod].c=max(max(aint[2*nod].c, aint[2*nod+1].c), aint[2*nod].b+aint[2*nod+1].a);

    }
    /*cout<<nod<<' '<<al<<' '<<ar<<endl;
    cout<<aint[nod].a<<' '<<aint[nod].b<<' '<<aint[nod].c<<endl<<endl;*/
}
int main(){
    fin>>n>>p;
    construire(1, 1, n);

    int o, a, b;
    while(p--){
        fin>>o;
        if(o==1){
            //cout<<1<<endl;
            fin>>a>>b;
            update(1, 1, n, a, a+b-1, -1);
        }
        else if(o==2){
            //cout<<-1<<endl;
            fin>>a>>b;
            update(1, 1, n, a, a+b-1, 1);
        }
        else{
            fout<<aint[1].c<<endl;
        }
    }
    return 0;
}