Cod sursa(job #3230885)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 23 mai 2024 10:39:39
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>

using namespace std;

const int NMAX = 1e5 + 5;
int st[NMAX*4], lazy[NMAX*4], ls, lsm;

void propagate(int l, int r, int node) {
    st[node] += lazy[node]*(r-l+1);
    if(l != r) {
        lazy[node<<1] += lazy[node];
        lazy[node<<1|1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int l, int r, int node, int ql, int qr, int cer) {
    if(ql > r || qr < l)
        return;
    if(ql <= l && r <= qr) {
        if(cer == 1) lazy[node]++;
        else lazy[node]--;
        propagate(l, r, node);
        return;
    }
    int mid = (l+r)/2;
    if(ql <= mid) update(l, mid, node<<1, ql, qr, cer);
    if(mid < qr) update(mid+1, r, node<<1|1, ql, qr, cer);
}

void query(int l, int r, int node) {
    propagate(l, r, node);
    if(st[node] == r-l+1) {
        lsm = max(ls, lsm);
        ls = 0;
        return;
    }
    if(st[node] == 0) {
        ls += (r-l+1);
        return;
    }
    int mid = (l+r)/2;
    query(l, mid, node<<1);
    query(mid+1, r, node<<1|1);
}

int main() {
    int n, q;
    cin >> n >> q;
    while(q--) {
        int cer;
        cin >> cer;
        if(cer < 3) {
            int a, b;
            cin >> a >> b;
            b += a - 1;
            update(1, n, 1, a, b, cer);
        }
        else {
            ls = 0;
            lsm = 0;
            query(1, n, 1);
            lsm = max(lsm ,ls);
            cout << lsm << '\n';
        }
    }
}