Cod sursa(job #2200858)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 2 mai 2018 20:40:13
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ("hotel.in");
ofstream g ("hotel.out");

int n, q, tip, l, r;

struct nod
{
    int st,dr,sol,lazy;
};
nod arb[100001 * 4];

void initializare (int nod, int a, int b)
{
    arb[nod].st = arb[nod].dr = arb[nod].sol = b - a + 1;
    if (a == b) return;
    int mij = (a + b) / 2;
    initializare (nod * 2, a, mij);
    initializare (nod * 2 + 1, mij + 1, b);
}

void propag (int nod, int a, int b)
{
    if (arb[nod].lazy == 0) return;
    if (arb[nod].lazy == 1)
    {
        arb[nod].st = arb[nod].dr = arb[nod].sol = 0;
    }
    else
    {
        arb[nod].st = arb[nod].dr = arb[nod].sol = b - a + 1;
    }
    if (a < b) arb[2 * nod].lazy = arb[2 * nod + 1].lazy = arb[nod].lazy;
    arb[nod].lazy = 0;
}

void update (int nod, int a, int b, int ua, int ub, int val)
{
    int mij = (a + b) / 2;
    if (ua <= a && b <= ub)
    {
        arb[nod].lazy = val;
        propag(nod,a,b);
        return;
    }

    propag(nod,a,b);
    if (ua <= mij) update (nod * 2, a, mij, ua, ub, val);
    else propag (nod * 2, a, mij);
    if (ub > mij) update (nod * 2 + 1, mij + 1, b, ua, ub, val);
    else propag (nod * 2 + 1, mij + 1, b);

    arb[nod].sol = max (arb[2 * nod].dr + arb[2 * nod + 1].st, max(arb[2 * nod].sol, arb[2 * nod + 1].sol));
    arb[nod].st = arb[2 * nod].st;
    if (arb[nod].st == mij - a + 1) arb[nod].st += arb[2 * nod + 1].st;
    arb[nod].dr = arb[2 * nod + 1].dr;
    if (arb[nod].dr == b - mij) arb[nod].dr += arb[2 * nod].dr;

}

int main()
{
    f >> n >> q;
    initializare(1,1,n);
    for (int i = 1; i <= q; i++)
    {
        f >> tip;
        if (tip == 3)
        {
            propag(1,1,n);
            g << arb[1].sol << '\n';
        }
        else
        {
            f >> l >> r;
            r += l-1;
            update(1,1,n,l,r,tip);
        }
    }
    return 0;
}