Cod sursa(job #2793787)

Utilizator gripzStroescu Matei Alexandru gripz Data 4 noiembrie 2021 00:54:34
Problema Hotel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <iostream>

#define MAXN 100002

using namespace std;

struct camera
{
    int val;
    int suf;
    int pref;
    int lazy;
};

int N, P, Q, pos, M;
camera T[4*MAXN];

void build(int node, int st, int dr)
{
    if(st == dr)
    {
        T[node].val = 1;
        T[node].suf = 1;
        T[node].pref = 1;
        T[node].lazy = 0;
    }
    else
    {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        // stiu clar ca asta e cazul mereu la build
        T[node].val = T[2 * node].suf + T[2 * node + 1].pref;
        T[node].suf = T[node].val;
        T[node].pref = T[node].val;
        T[node].lazy = 0;
    }
}

void propagate(int node, int st, int dr)
{
    if(T[node].lazy != 0) {
    if(st != dr)
    {

        T[2 * node].lazy = T[node].lazy;
        T[2 * node + 1].lazy = T[node].lazy;
    }
    if(T[node].lazy == -1)
    {
        T[node].val = dr - st + 1;
        T[node].suf = T[node].val;
        T[node].pref = T[node].val;
        T[node].lazy = 0;
    }
    else if(T[node].lazy == 1)
    {
        T[node].val = 0;
        T[node].suf = 0;
        T[node].pref = 0;
        T[node].lazy = 0;
    }
    }
}

void update(int node, int st, int dr)
{
    propagate(node, st, dr);
    if(st == dr)
    {
        if(pos <= st && dr <= pos + M - 1) {
            if(Q == 2)
            {
                T[node].val = 1;
                T[node].pref = 1;
                T[node].suf = 1;
            }
            if(Q == 1)
            {
                T[node].val = 0;
                T[node].pref = 0;
                T[node].suf = 0;
            }
        }
    }
    else
    {
        int mid = (st + dr) / 2;
        if(pos <= st && dr <= pos + M - 1)
        {
            if(Q == 2)
            {
                T[node].lazy = -1;
            }
            if(Q == 1)
            {
                T[node].lazy = 1;
            }
            propagate(node, st, dr);
            return;
        }
        update(2 * node, st, mid);
        update(2 * node + 1, mid + 1, dr);

        if(T[2 * node + 1].suf == dr - mid)
        {
            T[node].suf = T[2 * node + 1].suf + T[2 * node].suf;
        }
        else
        {
            T[node].suf = T[2* node + 1].suf;
        }
        if(T[2 * node].pref == mid - st + 1)
        {
            T[node].pref = T[2 * node + 1].pref + T[2 * node].pref;
        }
        else
        {
            T[node].pref = T[2 * node].pref;
        }
        T[node].val = max(max(T[2 * node].val, T[2 * node + 1].val),T[2 * node].suf + T[2 * node + 1].pref);
    }
}

int main()
{
    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);

    cin >> N >> P;

    build(1, 1,  N);

    for(int i = 1; i <= P; i++)
    {
        cin >> Q;
        if(Q == 3)
        {
            cout << T[1].val << endl;
        }
        else
        {
            cin >> pos >> M;
            update(1, 1, N);
        }
    }

    return 0;
}