Cod sursa(job #2811596)

Utilizator mateitudordmDumitru Matei mateitudordm Data 2 decembrie 2021 18:08:27
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>

using namespace std;

ifstream cin("hotel.in");
ofstream cout("hotel.out");
struct camere
{
    int cs, cd, tot;
};
struct AINT
{
    int lazy[400001];
    camere aint[400001];
    void propag(int ind, int val, int st, int dr)
    {
        if (val < 0)
            aint[ind].tot = aint[ind].cs = aint[ind].cd = dr - st + 1;
        else if (val > 0)
            aint[ind].tot = aint[ind].cs = aint[ind].cd = 0;
        if (st != dr)
            lazy[2 * ind] += val, lazy[2 * ind + 1] += val;
    }
    void update(int ind, int val, int stu, int dru, int st, int dr)
    {
        if (lazy[ind] != 0)
        {
            propag(ind, lazy[ind], st, dr);
            lazy[ind] = 0;
        }
        if (st >= stu && dr <= dru)
            propag(ind, val, st, dr);
        else
        {
            if (stu <= (st + dr) / 2)
                update(2 * ind, val, stu, dru, st, (st + dr) / 2);
            if (dru > (st + dr) / 2)
                update(2 * ind + 1, val, stu, dru, (st + dr) / 2 + 1, dr);
            propag(2 * ind, lazy[2 * ind], st, (st + dr) / 2);
            propag(2 * ind + 1, lazy[2 * ind + 1], (st + dr) / 2 + 1, dr);
            lazy[2 * ind] = 0, lazy[2 * ind + 1] = 0;
            aint[ind].tot = max(aint[2 * ind].tot, max(aint[2 * ind + 1].tot, aint[2 * ind].cd + aint[2 * ind + 1].cs));
            if (aint[2 * ind].tot < (st + dr) / 2 - st + 1)
                aint[ind].cs = aint[2 * ind].cs;
            else
                aint[ind].cs = (st + dr) / 2 - st + 1 + aint[2 * ind + 1].cs;
            if (aint[2 * ind + 1].tot < dr - (st + dr) / 2)
                aint[ind].cd = aint[2 * ind + 1].cd;
            else
                aint[ind].cd = dr - (st + dr) / 2 + aint[2 * ind].cd;
        }
    }
    void build(int ind, int st, int dr)
    {
        aint[ind] = {dr - st + 1, dr - st + 1, dr - st + 1};
        if (st != dr)
        {
            build(2 * ind, st, (st + dr) / 2);
            build(2 * ind + 1, (st + dr) / 2 + 1, dr);
        }
    }
};
AINT v;

int main()
{
    int n, q, c, a, b, i, cn;
    cin >> n >> q;
    for (i = 1; i <= 4 * n; i++)
        v.lazy[i] = 0, v.aint[i] = {0, 0, 0};
    v.build(1, 1, n);
    while (q)
    {
        cin >> c;
        if (c == 1)
        {
            cin >> a >> b;
            v.update(1, 1, a, a + b - 1, 1, n);
        }
        else if (c == 2)
        {
            cin >> a >> b;
            v.update(1, -1, a, a + b - 1, 1, n);
        }
        else
            cout << v.aint[1].tot << '\n';
        q--;
    }
    return 0;
}