Cod sursa(job #2605743)

Utilizator bigmixerVictor Purice bigmixer Data 25 aprilie 2020 18:48:58
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
//#define int long long
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=100005;

int n,p;

struct nod{
    int tot,le,ri,len,lazy;
}aint[4*nmax];

void push(int l,int r,int nod){
    if(aint[nod].lazy>=1){
        aint[nod].tot=aint[nod].le=aint[nod].ri=aint[nod].lazy=0;
        if(l!=r){
            aint[2*nod].lazy++;
            aint[2*nod+1].lazy++;
        }
    }
    if(aint[nod].lazy<=-1){
        aint[nod].tot=aint[nod].le=aint[nod].ri=aint[nod].len;
        aint[nod].lazy=0;
        if(l!=r){
            aint[2*nod].lazy--;
            aint[2*nod+1].lazy--;
        }
    }
}

nod merge(nod a,nod b){
    nod res;
    res.len=(a.len+b.len);
    res.tot=max(a.tot,b.tot);
    res.tot=max(res.tot,a.ri+b.le);
    res.ri=b.ri+(b.ri==b.len)*a.ri;
    res.le=a.le+(a.le==a.len)*b.le;
    res.lazy=0;
    return res;
}

void build(int l,int r,int nod){
    if(l==r){
        aint[nod].tot=aint[nod].le=aint[nod].ri=aint[nod].len=1;
        aint[nod].lazy=0;
    }
    else{
        int mid=l+(r-l)/2;
        build(l,mid,2*nod);
        build(mid+1,r,2*nod+1);
        aint[nod]=merge(aint[2*nod],aint[2*nod+1]);
    }
}

void update(int l,int r,int le,int ri,int val,int nod){
    push(l,r,nod);
    if(l>ri || r<le) return;
    else if(l>=le && r<=ri){
        aint[nod].lazy+=val;
        push(l,r,nod);
    }
    else{
        int mid=l+(r-l)/2;
        update(l,mid,le,ri,val,2*nod);
        update(mid+1,r,le,ri,val,2*nod+1);
        aint[nod]=merge(aint[2*nod],aint[2*nod+1]);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ifstream cin("hotel.in");
    ofstream cout("hotel.out");
    cin >> n >> p;
    build(1,n,1);
    while(p--){
        int t;
        cin >> t;
        if(t==1){
            int x,y;
            cin >> x >> y;
            y=(x+y-1);
            update(1,n,x,y,1,1);
        }
        if(t==2){
            int x,y;
            cin >> x >> y;
            y=(x+y-1);
            update(1,n,x,y,-1,1);
        }
        if(t==3){
            cout << aint[1].tot << '\n';
        }
    }
}