Cod sursa(job #2804092)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 20 noiembrie 2021 21:06:52
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
    
struct data {
    int pref, suff, ans;
} t[400001];

bitset <400001> marked;
 
int a[100001];
int N, Q, Task, l, r;
 
data make_data(int val){
    data res;
    res.pref = res.suff = res.ans = val;
    return res;
}
 
data combine(const data &a, const data &b, int tm, int tl, int tr){
    data res;
    res.ans = max({a.ans, b.ans, a.suff + b.pref});
    res.pref = max(a.pref, a.pref + (a.pref == tm - tl + 1) * b.pref);
    res.suff = max(b.suff, b.suff + a.suff * (b.suff == tr - tm));
    return res;
}

void push(int v) {
    if(marked[v]) {
        t[v << 1] = t[v << 1 | 1] = t[v];
        marked[v << 1] = marked[v << 1 | 1] = 1;
        marked[v] = 0;
    }
}
 
data query(int v, int tl, int tr, int l, int r){
    if(l > r)
        return make_data(0);
    if(l <= tl && tr <= r)
        return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    return combine(query(v << 1, tl, tm, l, min(r, tm)), query(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r), tm, tl, tr);
}
 
void build(int v, int tl, int tr){
    if(tl == tr) {
        t[v] = make_data(1);
    } else {
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        t[v] = combine(t[v << 1], t[v << 1 | 1], tm, tl, tr);
    }
}
 
void update(int v, int tl, int tr, int l, int r, int new_val) {
    if(l > r)
        return;
    if(l == tl && tr == r) {
        t[v] = make_data(new_val);
        marked[v] = 1;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v << 1, tl, tm, l, min(r, tm), new_val);
        update(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, new_val);
        t[v] = combine(t[v << 1], t[v << 1 | 1], tm, tl, tr);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("hotel");

    cin >> N >> Q;
    build(1, 1, N);

    while(Q--) {
        cin >> Task;
        if(Task == 1) {
            cin >> l >> r;
            update(1, 1, N, l, l + r - 1, 0);
        }

        if(Task == 2) {
            cin >> l >> r;
            update(1, 1, N, l, l + r - 1, 1);
        }

        if(Task == 3) {
            cout << query(1, 1, N, 1, N).ans << "\n";
        }
    }

    return 0;
}