Cod sursa(job #2633548)

Utilizator OvidRata Ovidiu Ovid Data 7 iulie 2020 18:52:17
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
ifstream fin("hotel.in"); ofstream fout("hotel.out");
#define cin fin
#define cout fout


int n, p;
struct node{
int l, r, m, sz;
};
node seg[400010];
void build(int v, int l, int r){
int m=(l+r)/2;
if(l==r){
    seg[v].m=1; seg[v].r=1; seg[v].l=1; seg[v].sz=1; return;
}
build(2*v, l, m); build(2*v+1, m+1, r);
seg[v].sz=seg[2*v].sz+seg[v*2+1].sz;
seg[v].l=seg[v].sz;
seg[v].r=seg[v].sz;
seg[v].m=seg[v].sz;
}





void update1(int v, int tl, int tr, int l, int r){
if(l>r){return;}
if(tl==l && tr==r){
    seg[v].m=0; seg[v].l=0; seg[v].r=0; return;
}
int tm=(tl+tr)/2;


update1(v*2, tl, tm, l, min(r, tm));
update1(2*v+1, tm+1, tr, max(l, tm+1), r);

seg[v].m=max( max(seg[2*v].m, seg[2*v+1].m), seg[2*v].r+seg[2*v+1].l);
seg[v].r=seg[2*v+1].r;
seg[v].l=seg[2*v].l;

if(seg[2*v].m==seg[2*v].sz){
    seg[v].l=seg[2*v].sz+seg[2*v+1].l;
}

if(seg[2*v+1].m==seg[2*v+1].sz){
    seg[v].r=seg[2*v+1].m+seg[2*v].r;
}

seg[v].m=max(seg[v].m, max(seg[v].l, seg[v].r) );
//cout<<"v="<<v<<",tl="<<tl<<",tr="<<tr<<" || l="<<seg[v].l<<" m="<<seg[v].m<<" r="<<seg[v].r<<" sz="<<seg[v].sz<<"\n";
return;
}

void update2(int v, int tl, int tr, int l, int r, bool ps){
if(ps){seg[v].l=0; seg[v].m=0; seg[v].r=0;}
if(l>r){return;}
if(tl==l && tr==r){
    seg[v].m=seg[v].sz; seg[v].r=seg[v].sz; seg[v].l=seg[v].sz; return;
}

int ps2= (ps ||seg[v].m==0) ;

int tm=(tl+tr)/2;
update2(2*v, tl, tm, l, min(tm, r), ps2); update2(2*v+1, tm+1, tr, max(l, tm+1), r, ps2);



seg[v].m=max(max(seg[2*v].m, seg[2*v+1].m), seg[2*v+1].l+seg[2*v].r);
seg[v].l=seg[2*v].l; seg[v].r=seg[2*v+1].r;

if(seg[2*v].m==seg[2*v].sz){
    seg[v].l=seg[2*v].sz+seg[2*v+1].l;
}

if(seg[2*v+1].m==seg[2*v+1].sz){
    seg[v].r=seg[2*v+1].m+seg[2*v].r;
}

seg[v].m=max(seg[v].m, max(seg[v].l, seg[v].r) );
//cout<<"v="<<v<<",tl="<<tl<<",tr="<<tr<<" || l="<<seg[v].l<<" m="<<seg[v].m<<" r="<<seg[v].r<<" sz="<<seg[v].sz<<"\n";
return;
}




int32_t main(){
INIT
cin>>n>>p;
build(1, 1, n);


while(p--){
    int o; cin>>o;

    if(o==1){
    int i, m; cin>>i>>m;
    //cout<<"begin1\n";
    update1(1, 1, n, i, i+m-1); //cout<<"end1\n";
    }
    if(o==2){
            int i, m;cin>>i>>m;
           // cout<<"begin2\n";
    update2(1, 1, n, i, i+m-1, false); //cout<<"end2\n";
    }
    if(o==3){
    cout<<seg[1].m<<"\n";
    }

}


return 0;
}