Cod sursa(job #731990)

Utilizator deneoAdrian Craciun deneo Data 9 aprilie 2012 15:18:24
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("hotel.in");
ofstream fout("hotel.out");

#define MAXN 100100

struct arb {
    int l, r, length, rez, needupdate;
};

arb a[MAXN * 3];
int n, p;

inline arb merge(arb a, arb b) {
    arb rez;
    rez.l = a.l;
    if (a.l == a.length)
        rez.l += b.l;
    rez.r = b.r;
    if (b.l == b.length)
        rez.r += a.r;
    rez.length = a.length + b.length;
    rez.rez = max ( max(a.rez, b.rez), a.r + b.l );
    return rez;
}

inline void build (int nod, int st, int fn) {
    int m = (st + fn) / 2;
    if (st == fn) {
        a[nod].l = a[nod].r = a[nod].length = a[nod].rez = 1;
        a[nod].needupdate = 0;
        return;
    }
    build (nod * 2, st, m);
    build (nod * 2 + 1, m + 1, fn);
    a[nod] = merge (a[nod * 2], a[nod * 2 + 1]);
}

inline void update(int nod, int st, int fn, int ist, int ifn, int op) {
    int m = (st + fn) / 2;
    if ( st >= ist && fn <= ifn ) {
        if (op == 1)
            a[nod].l = a[nod].r = a[nod].rez = 0;
        else
            a[nod].l = a[nod].r = a[nod].rez = fn - st + 1;
        a[nod].needupdate = op;
        return;
    }
    if (a[nod].needupdate != 0) {
        update(nod * 2, st, m, st, m, a[nod].needupdate);
        update(nod * 2 + 1, m + 1, fn, m + 1, fn, a[nod].needupdate);
        a[nod].needupdate = 0;
    }
    if (ist <= m)
        update(nod * 2, st, m, ist, ifn, op);
    if (ifn > m)
        update(nod * 2 + 1, m + 1, fn, ist, ifn, op);
    a[nod] = merge(a[nod * 2], a[nod * 2 + 1]);
}

int main() {
    int i, op, st, elem;
    fin >> n >> p;
    build (1, 1 , n);
    for (i = 1; i <= p; ++i) {
        fin >> op;
        if (op == 3)
            fout << a[1].rez << "\n";
        else {
            fin >> st >> elem;
            update(1, 1, n, st, st + elem - 1, op);
        }
    }
    fout.close();
    return 0;
}