Cod sursa(job #3141343)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 13 iulie 2023 18:07:39
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <bits/stdc++.h>
using namespace std;

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

struct mazan{
    int lmax, sufmax, prefmax;
    int l;
    int lazy = -1;
} aint[400001];

mazan join(mazan a, mazan b)
{
    mazan rasp;
    rasp.lmax = max(max(a.lmax, b.lmax), a.sufmax + b.prefmax);
    rasp.l = a.l + b.l;
    if(a.prefmax == a.l)
        rasp.prefmax = a.l + b.prefmax;
    else
        rasp.prefmax = a.prefmax;
    if(b.sufmax == b.l)
        rasp.sufmax = a.sufmax + b.l;
    else
        rasp.sufmax = b.sufmax;
    return rasp;
}

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod].lmax = aint[nod].prefmax = aint[nod].sufmax = aint[nod].l = 1;
        return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
    aint[nod] = join(aint[2 * nod], aint[2 * nod + 1]);
}

void propag(int nod, int st, int dr)
{
    if(st == dr || aint[nod].lazy == -1)
        return;
    if(aint[nod].lazy == 0)
    {
        aint[2 * nod].lmax = aint[2 * nod].prefmax = aint[2 * nod].sufmax = aint[2 * nod].l;
        aint[2 * nod + 1].lmax = aint[2 * nod + 1].prefmax = aint[2 * nod + 1].sufmax = aint[2 * nod + 1].l;
    }
    else
    {
        aint[2 * nod].lmax = aint[2 * nod].prefmax = aint[2 * nod].sufmax = 0;
        aint[2 * nod + 1].lmax = aint[2 * nod + 1].prefmax = aint[2 * nod + 1].sufmax = 0;
    }
    aint[2 * nod].lazy = aint[2 * nod + 1].lazy = aint[nod].lazy;
    aint[nod].lazy = -1;
}

void update(int nod, int st, int dr, int a, int b, bool x)
{
    if(b < st || dr < a)
        return;
    if(a <= st && dr <= b)
    {
        if(x == 0)
        {
            aint[nod].lmax = aint[nod].prefmax = aint[nod].sufmax = aint[nod].l;
            aint[nod].lazy = 0;
        }
        else
        {
            aint[nod].lmax = aint[nod].prefmax = aint[nod].sufmax = 0;
            aint[nod].lazy = 1;
        }
        return;
    }
    propag(nod, st, dr);
    int mid = (st + dr) / 2;
    update(2 * nod, st, mid, a, b, x);
    update(2 * nod + 1, mid + 1, dr, a, b, x);
    aint[nod] = join(aint[2 * nod], aint[2 * nod + 1]);
}

/*mazan query(int nod, int st, int dr, int a, int b)
{
    if(b < st || dr < a)
        return {0, 0, 0, 0, -1};
    if(a <= st && dr <= b)
        return aint[nod];
    propag(nod, st, dr);
    int mid = (st + dr) / 2;
    return join(query(2 * nod, st, mid, a, b),
                query(2 * nod + 1, mid + 1, dr, a, b));
}*/

int main()
{
    int n, m, t, a, b;
    in >> n >> m;
    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        in >> t;
        if(t == 3)
            out << aint[1].lmax << '\n';
        else
        {
            in >> a >> b;
            if(t == 1)
                update(1, 1, n, a, a + b - 1, 1);
            else
                update(1, 1, n, a, a + b - 1, 0);
        }
    }
    return 0;
}