Cod sursa(job #3125030)

Utilizator matei0000Neacsu Matei matei0000 Data 1 mai 2023 14:14:23
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <iostream>
#include <fstream>

using namespace std;
struct nod
{
    long long int pref, suf, secv, lazy, lg;
}v[800005];
void propag(long long int poz)
{
    if (v[poz].lazy==-1)
    {
        v[poz].pref=v[poz].lg;
        v[poz].suf=v[poz].lg;
        v[poz].secv=v[poz].lg;
        v[2*poz].lazy=v[poz].lazy;
        v[2*poz+1].lazy=v[poz].lazy;
    }
    if (v[poz].lazy==1)
    {
        v[poz].pref=0;
        v[poz].suf=0;
        v[poz].secv=0;
        v[2*poz].lazy=v[poz].lazy;
        v[2*poz+1].lazy=v[poz].lazy;
    }
        v[poz].lazy=0;
        return;
}
nod join(nod a, nod b)
{
    nod x;
    x.lazy=0;
    x.lg=a.lg+b.lg;
    x.secv=max(a.secv, max(b.secv, (a.suf+b.pref)));
    if (a.pref==a.lg)
        x.pref=(a.lg+b.pref);
    else
        x.pref=a.pref;
    if (b.suf==b.lg)
        x.suf=(a.suf+b.lg);
    else
        x.suf=b.suf;

        return x;
}
void build(long long int l, long long int r, long long int cr)
{
    if (l==r)
    {
        v[cr].secv=1;
        v[cr].pref=1;
        v[cr].suf=1;
        v[cr].lg=1;
        v[cr].lazy=0;
        return;
    }
    long long int mid=(l+r)/2;
    build(l, mid, 2*cr);
    build(mid+1, r, 2*cr+1);
    v[cr]=join(v[2*cr], v[2*cr+1]);
    return;
}
void update(long long int l, long long int r, long long int cr, long long int x, long long int y, long long int ind)
{
    propag(cr);
    if (x<=l&&r<=y)
    {
        if (ind==-1)
        {
            v[cr].lazy=-1;
            propag(cr);
        }
        else
        {
            v[cr].secv=v[cr].suf=v[cr].pref=0;
            v[2*cr].lazy=v[2*cr+1].lazy=ind;
        }
        return;
    }
    long long int mid=(l+r)/2;
    if (x<=mid)
        update(l, mid, 2*cr, x, y, ind);
    else
        propag(2*cr);
    if (mid<y)
        update(mid+1, r, 2*cr+1, x, y, ind);
    else
        propag(2*cr+1);
    v[cr]=join(v[2*cr], v[2*cr+1]);
    return;
}
int main()
{
    ifstream cin ("hotel.in");
    ofstream cout ("hotel.out");
    long long int n, q, cer, a, b;
    cin>>n>>q;
    build(1, n, 1);
    for (long long int i=0; i<q; i++)
    {
        cin>>cer;
        if (cer==3)
           cout<<v[1].secv<<'\n';
        else if (cer==2)
        {
            cin>>a>>b;
            update(1, n, 1, a, a+b-1, -1);
        }
        else
        {
            cin>>a>>b;
            update(1, n, 1, a, a+b-1, 1);
        }
    }
}