Cod sursa(job #2619566)

Utilizator drknss_Hehe hehe drknss_ Data 27 mai 2020 23:20:49
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 0x3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 500;
const int NMAX = 1e4 + 11;
const ll INF64 = 3e18 + 1;
const double lil = 0.0000000000001;

ifstream in("hotel.in");
ofstream out("hotel.out");

int n,a[N],mx[4*N],dr[4*N],st[4*N], lazy[4*N], len[4*N],q;

void build(int v, int l, int r){

    if(l == r){
        len[v] = 1;
        mx[v] = 1;
        st[v] = 1;
        dr[v] = 1;
    }else{

        int mid = (l+r)/2;

        build(2*v,l,mid);
        build(2*v+1,mid+1,r);

        len[v] = len[2*v] + len[2*v + 1];
        mx[v] = mx[2*v] + mx[2*v + 1];
        st[v] = mx[v];
        dr[v] = mx[v];
    }
}


void update(int v,int tl,int tr,int l,int r,int val){

    if(lazy[v]){

        mx[v] = (lazy[v] > 0 ? len[v] : 0);
        st[v] = (lazy[v] > 0 ? len[v] : 0);
        dr[v] = (lazy[v] > 0 ? len[v] : 0);

        if(tl != tr){
            lazy[2*v] += lazy[v];
            lazy[2*v + 1] += lazy[v];
        }
        lazy[v] = 0;
    }


    if(tl > tr || tl > r || tr < l || l > r)return;

    if(l <= tl && tr <= r){

        mx[v] = (val > 0 ? len[v] : 0);
        st[v] = (val > 0 ? len[v] : 0);
        dr[v] = (val > 0 ? len[v] : 0);

        if(tl != tr){
            lazy[2*v] += val;
            lazy[2*v + 1] += val;
        }

        return;
    }


    int mid = (tl + tr)/2;

    update(2*v, tl, mid, l, r,val);
    update(2*v + 1, mid + 1, tr, l, r,val);

    if(st[2*v] == len[2*v]){
        st[v] = st[2*v] + st[2*v + 1];
    }else{
        st[v] = st[2*v];
    }

    if(dr[2*v + 1] == len[2*v + 1]){
        dr[v] = dr[2*v] + dr[2*v + 1];
    }else{
        dr[v] = dr[2*v + 1];
    }

    mx[v] = max({mx[2*v+1],mx[2*v],dr[2*v]+st[2*v+1]});
}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();


    in >> n >> q;

    build(1,1,n);

    while(q--){

        int x;

        in >> x;

        if(x == 1){
            int y,siz;

            in >> y >> siz;

            update(1,1,n,y,y + siz - 1, -1);
        }

        if(x == 2){
            int y,siz;

            in >> y >> siz;

            update(1,1,n,y,y + siz - 1, 1);
        }

        if(x == 3){
            out << mx[1] << '\n';
        }
    }

}