Cod sursa(job #3160571)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 24 octombrie 2023 17:19:16
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#define sz 100000
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");


int n,p;

struct NNodNN
{
    int lazy = 0;
    int pref;
    int suf;
    int secv;
    int sum;
    int l;
};

NNodNN a[4*sz + 5];

void UpdateNodLazy(int nod,int st,int dr)
{
    if(a[nod].lazy==0)
        return;
    if(st!=dr)
    {
        a[nod*2].lazy  += a[nod].lazy;
        a[nod*2+1].lazy  += a[nod].lazy;
    }
    a[nod].sum += a[nod].lazy;

    if(a[nod].sum == 0)
    {
        a[nod].pref=0;
        a[nod].suf=0;
        a[nod].secv=0;
        a[nod].sum=0;
    }
    else
    {   a[nod].pref=a[nod].l;
        a[nod].suf=a[nod].l;
        a[nod].secv=a[nod].l;
        a[nod].sum=a[nod].l;
    }

    a[nod].lazy = 0;
}
NNodNN UpdateNodBest(NNodNN a,NNodNN b)
{
    NNodNN c;
    c.sum = a.sum + b.sum;
    c.pref = a.pref;
    if(a.pref == a.l)
        c.pref += b.pref;
    c.suf = b.suf;
    if(b.suf == b.l)
        c.suf += a.suf;
    c.secv = max (  max(a.secv , b.secv), a.suf + b.pref );
    c.l = a.l + b.l;
    return c;
}

void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod].l = 1;
        a[nod].pref =1;
        a[nod].suf = 1;
        a[nod].secv =1;
        a[nod].sum = 1;
        return;
    }
    int mid=(st+dr)/2;
    build(nod*2,st,mid);
    build(nod*2+1,mid+1,dr);
    a[nod]= UpdateNodBest(a[nod*2],a[nod*2+1]);
}

void update(int nod,int st,int dr,int x,int y,int val)
{
    UpdateNodLazy(nod,st,dr);
    if(x<=st && dr<=y)
    {
        a[nod].lazy = val;
        UpdateNodLazy(nod,st,dr);
        return;
    }
    int mid = (st+dr)/2;
    if(x<=mid)
        update(nod*2,st,mid,x,y,val);
    if(y>mid)
        update(nod*2+1,mid+1,dr,x,y,val);
    UpdateNodLazy(nod*2,st,mid);
    UpdateNodLazy(nod*2+1,mid+1,dr);
    a[nod] = UpdateNodBest(a[nod*2],a[nod*2+1]);
}
NNodNN query(int nod,int st,int dr,int x,int y)
{
    UpdateNodLazy(nod,st,dr);
    if(x<=st && dr<=y)
        return a[nod];
    int mid = (st+dr)/2;
    if(y <=mid)
        return query(nod*2,st,mid,x,y);
    else if (x > mid)
        return query(nod*2+1,mid+1,dr,x,y);
    else
        return UpdateNodBest(query(nod*2,st,mid,x,y),query(nod*2+1,mid+1,dr,x,y));
}



int main()
{
    fin>>n>>p;
    build(1,1,n);
    for(int i=1;i<=p;i++)
    {
        int t;
        fin>>t;
        if(t==1)
        {
            int a,b;
            fin>>a>>b;
            update(1,1,n,a,a+b-1,-1);
        }
        else if(t==2)
        {
            int a,b;
            fin>>a>>b;
            update(1,1,n,a,a+b-1,1);
        }
        else
        {
            fout<<query(1,1,n,1,n).secv<<'\n';
        }
    }
}