Cod sursa(job #3156301)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 11 octombrie 2023 10:07:40
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

string nume="hotel";
ifstream in(nume+".in");
ofstream out(nume+".out");
#define cin in
#define cout out

const int MN=1e5+5;

int mst[MN<<2],mdr[MN<<2], mmid[MN<<2];
int lazy[MN<<2];
int n,q;

void down(int nod, int st, int dr)
{
    if(lazy[nod]==0) return;
    mst[nod]=mdr[nod]=mmid[nod]=mmid[nod]+(dr-st+1)*lazy[nod];
    if(st!=dr)
    {
        lazy[nod<<1]+=lazy[nod];
        lazy[nod<<1^1]+=lazy[nod];
    }
    lazy[nod]=0;
}

void update(int nod,int st, int dr,int qst, int qdr, int val)
{
    down(nod,st,dr);
    if(qdr<st||dr<qst) return;
    
    if(qst<=st&&dr<=qdr)
    {

        lazy[nod]=lazy[nod]+val;
        down(nod,st,dr);
        return;
    }
    
    int mid=(st+dr)/2;
    update(nod<<1,    st,mid,qst,qdr,val);
    update(nod<<1^1,mid+1,dr,qst,qdr,val);
    
    mst[nod]=mst[nod<<1];
    if(mst[nod]==mid-st+1) mst[nod]+=mst[nod<<1^1];
    mdr[nod]=mdr[nod<<1^1];
    if(mdr[nod]==dr-mid) mdr[nod]+=mdr[nod<<1];
    
    mmid[nod]=max(mdr[nod<<1]+mst[nod<<1^1], max(mmid[nod<<1], mmid[nod<<1^1]));
}

int main()
{
    cin>>n>>q;
    int a,b,c;
    update(1,1,n,1,n,1);
    for(int i=1;i<=q;i++)
    {
        cin>>c;
        if(c==3)
        {
            cout<<mmid[1]<<'\n';
        }
        else
        {
            cin>>a>>b;
            update(1,1,n,a,a+b-1, c==1?-1:1);
            
        }
    }
    return 0;
}