Cod sursa(job #3125024)

Utilizator andystarzSuna Andrei andystarz Data 1 mai 2023 14:07:28
Problema Hotel Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <fstream>

using namespace std;
struct andi
{
    int sl, sr, secv, lazy, len;
}v[400005];
void propag(int poz)
{
    if (v[poz].lazy==-1)
    {
        v[poz].sl=v[poz].len;
        v[poz].sr=v[poz].len;
        v[poz].secv=v[poz].len;
        v[2*poz].lazy=v[poz].lazy;
        v[2*poz+1].lazy=v[poz].lazy;
    }
    if (v[poz].lazy==1)
    {
        v[poz].sl=0;
        v[poz].sr=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;
}
andi join(andi a, andi b)
{
    andi amog;
    amog.lazy=0;
    amog.len=a.len+b.len;
    amog.secv=max(a.secv, max(b.secv, (a.sr+b.sl)));
    if (a.sl==a.len)
        amog.sl=(a.len+b.sl);
    else
        amog.sl=a.sl;
    if (b.sr==b.len)
        amog.sr=(a.sr+b.len);
    else
        amog.sr=b.sr;

        return amog;
}
void build(int l, int r, int cr)
{
    if (l==r)
    {
        v[cr].secv=1;
        v[cr].sl=1;
        v[cr].sr=1;
        v[cr].len=1;
        v[cr].lazy=0;
        return;
    }
    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(int l, int r, int cr, int x, int y, int ind)
{
    propag(cr);
    if (x<=l&&r<=y)
    {
        if (ind==-1)
        {
            v[cr].lazy=-1;
            propag(cr);
        }
        else
        {
            v[cr].secv=v[cr].sr=v[cr].sl=0;
            v[2*cr].lazy=v[2*cr+1].lazy=ind;
        }
        return;
    }
    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");
    int n, q, cer, a, b;
    cin>>n>>q;
    build(1, n, 1);
    for (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);
        }
    }
}