Cod sursa(job #2516441)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 31 decembrie 2019 15:04:26
Problema Hotel Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");

int val, L, R, maxi, v, q;

struct arb
{
    int l_s, l_d, l_max;
};

const int NMAX = 100001;

arb a[4 * NMAX];

void update(int nod, int left, int right)
{
    if (left > right) return;

    if (left == right)
    {
        if (q == 1)
        {
            if (L <= left && right <= R)
            {
                a[nod].l_s = a[nod].l_d = 0;
                a[nod].l_max = -1;
            }
            else if (a[nod].l_max >= 0) a[nod].l_s = a[nod].l_d = a[nod].l_max = 1;
        }
        else
        {
            if (L <= left && right <= R) a[nod].l_s = a[nod].l_d = a[nod].l_max = 1;
        }
        return;
    }

    int m = (left + right) / 2;

    update(2 * nod, left, m);
    update(2 * nod + 1, m + 1, right);

    a[nod].l_s = a[2 * nod].l_s;
    a[nod].l_d = a[2 * nod + 1].l_d;

    if (a[2 * nod].l_s == a[2 * nod].l_d  && a[2 * nod].l_d == m - left + 1)
        a[nod].l_s  += a[2 * nod + 1].l_s;

    if (a[1 + 2 * nod].l_s == a[2 * nod + 1].l_d && a[2 * nod + 1].l_d == right - m)
        a[nod].l_d += a[2 * nod].l_d;

    a[nod].l_max = max(max(a[2 * nod].l_max, a[2 * nod + 1].l_max), max(max(a[nod].l_s, a[nod].l_d),a[2 * nod + 1].l_s + a[2 * nod].l_d));

}

int n, p, i, m;

int main()
{
    bool ok = false;
    fin >> n >> p;
    while (p--)
    {
        fin >> q;
        if (q == 3)
        {
            if (ok) fout << a[1].l_max << "\n";
            else fout << n << "\n";
        }
        else
        {
            ok = true;

            fin >> L >> R;

            R = L + R - 1;

            update(1, 1, n);
        }
    }
    return 0;
}