Cod sursa(job #2795278)

Utilizator gripzStroescu Matei Alexandru gripz Data 6 noiembrie 2021 10:31:18
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.79 kb
#include <algorithm>
#include <cctype>
#include <cstdio>

#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 (pos <= st && dr <= pos + M - 1) {
        if (Q == 2)
            T[node].lazy = -1;
        if (Q == 1)
            T[node].lazy = 1;
        propagate(node, st, dr);
    } else {
        int mid = (st + dr) / 2;

        if (pos <= mid)
            update(2 * node, st, mid);
        if (pos + M - 1 > mid)
            update(2 * node + 1, mid + 1, dr);

        T[node].suf = T[2 * node + 1].suf;
        if (T[2 * node + 1].suf == dr - mid) {
            T[node].suf = T[2 * node + 1].suf + T[2 * node].suf;
        }

        T[node].pref = T[2 * node].pref;
        if (T[2 * node].pref == mid - st + 1) {
            T[node].pref = T[2 * node + 1].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;
}