Cod sursa(job #3363500)

Utilizator Alexutu008Ionita Alexandru-Dumitru Alexutu008 Data 18 august 2026 17:23:36
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>

using namespace std;
const int max_size = 1e5 + 1, max_seg = 4e5 + 1;

int n, q, op, i, gsize, v[max_size], lazy[max_seg],
    best[max_seg], suf[max_seg], pref[max_seg], sum[max_seg];
// v[i] = is_free[i]

void init(int l, int r, int nod)
{
    if (l == r)
    {
        pref[nod] = suf[nod] = best[nod] = sum[nod] = v[l];
        return;
    }
    int m = (l + r) / 2;
    init(l, m, nod * 2);
    init(m + 1, r, nod * 2 + 1);
    pref[nod] = (sum[nod * 2] == m - l + 1) ? sum[nod * 2] + pref[nod * 2 + 1] : pref[nod * 2];
    suf[nod] = (sum[nod * 2 + 1] == r - m) ? sum[nod * 2 + 1] + suf[nod * 2] : suf[nod * 2 + 1];
    sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
    best[nod] = max(max(best[nod * 2], best[nod * 2 + 1]), suf[nod * 2] + pref[nod * 2 + 1]);
}

void push(int l, int r, int nod)
{
    if (l != r && lazy[nod])
    {
        lazy[nod << 1] += lazy[nod];
        sum[nod << 1] += lazy[nod] * ((l + r) / 2 - l + 1);
        lazy[(nod << 1) + 1] += lazy[nod];
        sum[(nod << 1) + 1] += lazy[nod] * (r - (l + r) / 2);

        pref[(nod << 1)] = suf[(nod << 1)] = best[(nod << 1)] = sum[(nod << 1)];
        pref[(nod << 1) + 1] = suf[(nod << 1) + 1] = best[(nod << 1) + 1] = sum[(nod << 1) + 1];
    }
    lazy[nod] = 0;
}

void update(int l, int r, int st, int dr, int val, int nod)
{
    if (st <= l && r <= dr)
    {
        lazy[nod] += val;
        sum[nod] += val * (r - l + 1);
        pref[nod] = suf[nod] = best[nod] = sum[nod];
        return;
    }
    push(l, r, nod);
    int m = l + r >> 1;
    if (st <= m)
        update(l, m, st, dr, val, nod << 1);
    if (m + 1 <= dr)
        update(m + 1, r, st, dr, val, (nod << 1) + 1);
    pref[nod] = (sum[nod * 2] == m - l + 1) ? sum[nod * 2] + pref[nod * 2 + 1] : pref[nod * 2];
    suf[nod] = (sum[nod * 2 + 1] == r - m) ? sum[nod * 2 + 1] + suf[nod * 2] : suf[nod * 2 + 1];
    sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
    best[nod] = max(max(best[nod * 2], best[nod * 2 + 1]), suf[nod * 2] + pref[nod * 2 + 1]);
}

int main()
{
    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        v[i] = 1;
    init(1, n, 1);

    while (q--)
    {
        cin >> op;
        if (op == 3)
        {
            cout << best[1] << '\n';
        }
        else
        {
            cin >> i >> gsize;
            if (op == 2)
                update(1, n, i, i + gsize - 1, 1, 1);
            else
                update(1, n, i, i + gsize - 1, -1, 1);
        }
    }

    return 0;
}