Cod sursa(job #2793792)

Utilizator gripzStroescu Matei Alexandru gripz Data 4 noiembrie 2021 01:01:39
Problema Hotel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.47 kb
#include <cstdio>
#include <algorithm>
#include <cctype>

#define MAXN 100002

using namespace std;


class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

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()
{
    InParser fin("hotel.in");
    FILE *out = fopen("hotel.out", "w");

    fin >> N >> P;

    build(1, 1,  N);

    for(int i = 1; i <= P; i++)
    {
        fin >> Q;
        if(Q == 3)
        {
            fprintf(out, "%d\n", T[1].val);
        }
        else
        {
            fin >> pos >> M;
            update(1, 1, N);
        }
    }

    return 0;
}