Cod sursa(job #3182950)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 10 decembrie 2023 12:26:22
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>

using namespace std;
ifstream in("hotel.in");
ofstream out("hotel.out");
const int N = 1e5;

struct tree_type {
    int pref, suf, ans, sz;
};

int n, q;
tree_type tree[4*N];

void build(int nod, int st, int dr) {
    tree[nod].pref = tree[nod].suf = tree[nod].ans = tree[nod].sz = dr - st + 1;
    if(st < dr) {
        int mid = (st + dr) / 2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
    }
}
void update(int nod, int st, int dr, int l, int r, bool scot) {
    if(l <= st && dr <= r) {
        if(scot)
            tree[nod].pref = tree[nod].suf = tree[nod].ans = 0;
        else
            tree[nod].pref = tree[nod].suf = tree[nod].ans = dr - st + 1;
    }
    else {
        int mid = (st + dr) / 2;
        if(l <= mid)
            update(2*nod, st, mid, l, r, scot);
        if(mid < r)
            update(2*nod+1, mid+1, dr, l, r, scot);

        tree[nod].pref = tree[2*nod].pref + (tree[2*nod].pref == tree[2*nod].sz ? tree[2*nod+1].pref : 0);
        tree[nod].suf = tree[2*nod+1].suf + (tree[2*nod+1].suf == tree[2*nod+1].sz ? tree[2*nod].suf : 0);
        tree[nod].ans = max(tree[2*nod].suf + tree[2*nod].pref, max(tree[2*nod].ans, tree[2*nod+1].ans));
    }
}

int main()
{
    in >> n >> q;
    build(1, 1, n);
    while(q--) {
        int tip;
        in >> tip;
        if(tip == 1) {
            int start, lg, fin;
            in >> start >> lg;
            fin = start + lg - 1;
            update(1, 1, n, start, fin, 1);
        }
        else if(tip == 2) {
            int start, lg, fin;
            in >> start >> lg;
            fin = start + lg - 1;
            update(1, 1, n, start, fin, 0);
        }
        else out << tree[1].ans << '\n';
    }
    return 0;
}