Cod sursa(job #1911232)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 7 martie 2017 19:50:13
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define DIM 400000

struct elem {
    int mx;
    int lf;
    int rg;
} arbint[DIM];

int N, M;

void update(int nod, int st, int dr, int a, int b, int tip) {
    if(a <= st && dr <= b) {
        if(tip == 1) {
            arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = 0;
        }
        else {
            arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = dr - st + 1;
        }

        return ;
    }

    int mij = (st + dr) / 2;

    if(arbint[nod].mx == 0) {
        arbint[2 * nod].mx = arbint[2 * nod].lf = arbint[2 * nod].rg = 0;
        arbint[2 * nod + 1].mx = arbint[2 * nod + 1].lf = arbint[2 * nod + 1].rg = 0;
    }
    if(arbint[nod].mx == dr - st + 1) {
        arbint[2 * nod].mx = arbint[2 * nod].lf = arbint[2 * nod].rg = mij - st + 1;
        arbint[2 * nod + 1].mx = arbint[2 * nod + 1].lf = arbint[2 * nod + 1].rg = dr - mij;
    }

    if(b > mij) {
        update(2 * nod + 1, mij + 1, dr, a, b, tip);
    }

    if(a <= mij) {
        update(2 * nod, st, mij, a, b, tip);
    }

    arbint[nod].mx = max(arbint[2 * nod].mx, max(arbint[2 * nod + 1].mx, arbint[2 * nod].rg + arbint[2 * nod + 1].lf));
    arbint[nod].lf = arbint[2 * nod].lf;
    if(arbint[nod].lf == mij - st + 1) {
        arbint[nod].lf += arbint[2 * nod + 1].lf;
    }

    arbint[nod].rg = arbint[2 * nod + 1].rg;
    if(arbint[nod].rg == dr - mij) {
        arbint[nod].rg += arbint[2 * nod].rg;
    }
}

void buildArb(int nod, int st, int dr) {
    if(st == dr) {
        arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = 1;
        return ;
    }

    int mij = (st + dr) / 2;

    buildArb(2 * nod, st, mij);
    buildArb(2 * nod + 1, mij + 1, dr);

    arbint[nod].mx = dr - st + 1;
    arbint[nod].rg = dr - st + 1;
    arbint[nod].lf = dr - st + 1;
}

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

    scanf("%d %d\n", &N, &M);

    buildArb(1, 1, N);

    int tip, x, y;
    while(M--) {
        scanf("%d", &tip);

        if(tip == 3) {
            cout << arbint[1].mx << '\n';
        }
        else {
            scanf("%d %d\n", &x, &y);

            update(1, 1, N, x, x + y - 1, tip);
        }
    }

    return 0;
}