Cod sursa(job #2664587)

Utilizator Iulia14iulia slanina Iulia14 Data 28 octombrie 2020 21:23:18
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>

using namespace std;
ifstream cin ("hotel.in");
ofstream cout ("hotel.out");
struct ura{
    int sol, pre, suf;
};
ura seg[400005];
void julie(int nod, int st, int dr)
{
    if (st == dr)
        seg[nod].sol = seg[nod].pre = seg[nod].suf = 1;
    else
    {
        int mid = (st + dr) / 2;
        julie(2 * nod, st, mid);
        julie(2 * nod + 1, mid + 1, dr);
        seg[nod].sol = seg[nod].pre = seg[nod].suf = seg[2 * nod].sol + seg[2 * nod + 1].sol;
    }
}
void update(int nod, int st, int dr, int l, int r, int tip)
{
    if (l <= st && dr <= r)
        seg[nod].sol = seg[nod].pre = seg[nod].suf = (dr - st + 1) * tip;
    else
    {
        int mid = (st + dr) / 2;
        if (seg[nod].sol == (1 - tip) * (dr - st + 1))
        {
            seg[2 * nod].sol = seg[2 * nod].pre = seg[2 * nod].suf = (mid - st + 1) * (1 - tip);
            seg[2 * nod + 1].sol = seg[2 * nod + 1].pre = seg[2 * nod + 1].suf = (dr - mid) * (1 - tip);
        }
        if (l <= mid)
            update(2 * nod, st, mid, l, r, tip);
        if (r > mid)
            update(2 * nod + 1, mid + 1, dr, l, r, tip);
        if (seg[2 * nod].sol == mid - st + 1)
            seg[nod].pre = seg[2 * nod].sol + seg[2 * nod + 1].pre;
        else
            seg[nod].pre = seg[2 * nod].pre;
        if (seg[2 * nod + 1].sol == dr - mid)
            seg[nod].suf = seg[2 * nod + 1].sol + seg[2 * nod].suf;
        else
            seg[nod].suf = seg[2 * nod + 1].suf;
        seg[nod].sol = max(seg[nod * 2].sol, seg[nod * 2 + 1].sol);
        seg[nod].sol = max(seg[nod].sol, seg[nod * 2].suf + seg[nod * 2 + 1].pre);
    }
}
int main()
{
    int n, k, i;
    cin >> n >> k;
    julie(1, 1, n);
    for (i = 1; i <= k; i++)
    {
        int cer, a, b;
        cin >> cer;
        if (cer == 3)
            cout << seg[1].sol << '\n';
        else
        {
            cin >> a >> b;
            update(1, 1, n, a, a + b - 1, cer - 1);
        }
    }
    return 0;
}