Cod sursa(job #3141923)

Utilizator andystarzSuna Andrei andystarz Data 17 iulie 2023 18:07:12
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>

using namespace std;
struct camera
{
    int pref, suf, len, nud;
    int lazy=-1;
    ///lazy 1 inseamna ca vin turisti
    ///lazy 0 inseamna ca pleaca turisti
    ///lazy -1 e initial
}v[400005];
void propag(int cr, int st, int dr)
{
    if (st==dr||v[cr].lazy==-1)
        return;
    if (v[cr].lazy==0)
    {
        v[2*cr].suf=v[2*cr].pref=v[2*cr].nud=v[2*cr].len;
        v[2*cr+1].suf=v[2*cr+1].pref=v[2*cr+1].nud=v[2*cr+1].len;
    }
    else
    {
        v[2*cr].suf=v[2*cr].pref=v[2*cr].nud=0;
        v[2*cr+1].suf=v[2*cr+1].pref=v[2*cr+1].nud=0;
    }
    v[2*cr].lazy=v[2*cr+1].lazy=v[cr].lazy;
    v[cr].lazy=-1;
    return;
}
camera join(camera a, camera b)
{
    camera c;
    c.nud=max(max(a.nud, b.nud), (a.suf+b.pref));
    c.len=a.len+b.len;
    if (a.pref==a.len)
        c.pref=a.len+b.pref;
    else
        c.pref=a.pref;
    if (b.suf==b.len)
        c.suf=b.len+a.suf;
    else
        c.suf=b.suf;
    c.lazy=-1;
    return c;
}
void update(int l, int r, int ul, int ur, int cr, int val)
{
    if (ur<l||ul>r)
        return;
    if (ul<=l&&r<=ur)
    {
        v[cr].lazy=val;
        if (val==0)
        {
            v[cr].pref=v[cr].suf=v[cr].nud=v[cr].len;
        }
        else
        {
            v[cr].pref=v[cr].suf=v[cr].nud=0;
        }
        return;
    }
    int mid=(l+r)/2;
    propag(cr, l, r);
    update(l, mid, ul, ur, 2*cr, val);
    update(mid+1, r, ul, ur, 2*cr+1, val);
    v[cr]=join(v[2*cr], v[2*cr+1]);
    return;
}
void build(int l, int r, int cr)
{
    if (l==r)
    {
        v[cr].pref=v[cr].suf=v[cr].nud=v[cr].len=1;
        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;
}
int main()
{
    ifstream cin ("hotel.in");
    ofstream cout ("hotel.out");
   int n, p, cer, a, b;
   cin>>n>>p;
   build (1, n, 1);
   for (int i=0; i<p; i++)
   {
       cin>>cer;
       if (cer==1)
       {
           cin>>a>>b;
           update(1, n, a, a+b-1, 1, 1);
           //printamongturip(n);
       }
       else if (cer==2)
       {
           cin>>a>>b;
           update(1, n, a, a+b-1, 1, 0);
           //printamongturip(n);
       }
       else if (cer==3)
       {
           cout<<v[1].nud<<'\n';
       }
   }
}