Cod sursa(job #1767644)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 29 septembrie 2016 16:06:19
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<fstream>

using namespace std;

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

const int nmax = 1e5;

struct Nod{
    int st, dr, cate, lg;
    int lazy;
} aint[4 * nmax + 1];

inline int max2 (int a, int b) {
    return (a < b ? b : a);
}
inline int max3 (int a, int b, int c) {
    return max2(a, max2(b, c));
}
inline Nod cu_lazy (Nod x) {
    if (x.lazy == 1) {
        x.st = x.dr = 0;
        x.cate = 0;
    } else if (x.lazy == 2) {
        x.st = x.dr = x.cate = x.lg;
    }
    return x;
}
inline Nod uneste (Nod x, Nod y) {
    Nod sol;
    x = cu_lazy( x ), y = cu_lazy( y );

    sol.lg = x.lg + y.lg;

    if (x.cate == x.lg) {
        sol.st = x.lg + y.st;
    } else {
        sol.st = x.st;
    }

    if (y.cate == y.lg) {
        sol.dr = y.lg + x.dr;
    } else {
        sol.dr = y.dr;
    }

    sol.cate = max3(sol.st, sol.dr, x.dr + y.st);
    sol.lazy = 0;
    return sol;
}
inline void propaga (int nod) {
    aint[2 * nod].lazy = aint[2 * nod + 1].lazy = aint[ nod ].lazy;
    aint[2 * nod] = cu_lazy(aint[2 * nod]);
    aint[2 * nod + 1] = cu_lazy(aint[2 * nod + 1]);
    aint[ nod ].lazy = 0;
}
void build (int nod, int x, int y) {
    if (x == y) {
        aint[ nod ].cate = aint[ nod ].lg = 1;
        aint[ nod ].st = aint[ nod ].dr = 1;
        aint[ nod ].lazy = 0;
        return ;
    }

    int mij = (x + y) / 2;
    build(2 * nod, x, mij); build(2 * nod + 1, mij + 1, y);
    aint[ nod ] = uneste(aint[2 * nod], aint[2 * nod + 1]);
}
void update (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aint[ nod ].lazy = val;
        aint[ nod ] = cu_lazy(aint[ nod ]);
        return ;
    }

    int mij = (x + y) / 2;
    if (aint[ nod ].lazy > 0)
        propaga( nod );

    if (st <= mij) {
        update(2 * nod, x, mij, st, dr, val);
    }
    if (mij < dr) {
        update(2 * nod + 1, mij + 1, y, st, dr, val);
    }
    aint[ nod ] = uneste(aint[2 * nod], aint[2 * nod + 1]);
}
int main() {
    int n, p;
    fin >> n >> p;

    build(1, 1, n);

    while (p --) {
        int t, x, y;
        fin >> t;
        if (t == 1) {
            fin >> x >> y;
            update(1, 1, n, x, x + y - 1, 1);
        } else if (t == 2) {
            fin >> x >> y;
            update(1, 1, n, x, x + y - 1, 2);
        } else {
            fout << cu_lazy(aint[ 1 ]).cate << "\n";
        }
    }

    fin.close();
    fout.close();
    return 0;
}