Cod sursa(job #3160584)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 24 octombrie 2023 17:31:42
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 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;
};

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;
    }
    if(a[nod].lazy==1)
    {
        a[nod].pref=dr-st+1;
        a[nod].suf=dr-st+1;
        a[nod].secv=dr-st+1;
    }
    else
    {
        a[nod].pref=0;
        a[nod].suf=0;
        a[nod].secv=0;
    }


    a[nod].lazy = 0;
}
NNodNN UpdateNodBest(NNodNN a,NNodNN b,int st,int dr,int mid)
{
    NNodNN c;
    c.pref = a.pref;
    if(a.pref == mid-st+1)
        c.pref += b.pref;
    c.suf = b.suf;
    if(b.suf == dr-mid)
        c.suf += a.suf;
    c.secv = max (  max(a.secv , b.secv), a.suf + b.pref );
    return c;
}

void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod].pref =1;
        a[nod].suf = 1;
        a[nod].secv =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],st,dr,mid);
}

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],st,dr,mid);
}
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),st,dr,mid);
}



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';
        }
    }
}