Cod sursa(job #3141347)

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

const int val = 1 << 12;

char next_char()
{
    static char buff[val];
    static int bp=val;
    if(bp==val)
    {
        bp=0;
        fread(buff,1,val,stdin);
    }
    return buff[bp++];
}
void get(int &a)
{
    a = 0;
    char ch;
    do{
        ch=next_char();
    }while('0'>ch||ch>'9');
    do{
        a=a*10+(ch-'0');
        ch=next_char();
    }while('0'<=ch&&ch<='9');
}

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()
{
    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);
    int n, m, t, a, b;
    get(n);
    get(m);
    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        get(t);
        if(t == 3)
            cout << aint[1].lmax << '\n';
        else
        {
            get(a);
            get(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;
}