Cod sursa(job #2065285)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 13 noiembrie 2017 17:57:47
Problema Hotel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <cmath>
#define DIM 100002

using namespace std;

ifstream f("hotel.in");
ofstream g("hotel.out");

int n, m, flag[4 * DIM], tip, x, y, cobor[4 * DIM];

struct arbore{
    int smij, sst, sdr, complet;
}aint[4 * DIM];

void updatelazy(int nod, int st, int dr){
    if(flag[nod] == 1)
        aint[nod].sst = aint[nod].sdr = aint[nod].smij = dr - st + 1;
    if(flag[nod] == -1)
        aint[nod].sst = aint[nod].sdr = aint[nod].smij = 0;
    if(flag[nod]){
        if(st != dr)
            flag[nod<<1] = flag[nod<<1|1] = flag[nod];
        flag[nod] = 0;
    }
}

void updatenod(int nod, int st, int dr){
    aint[nod].smij = max(max(aint[nod<<1].smij, aint[nod<<1|1].smij), aint[nod<<1].sdr + aint[nod<<1|1].sst);
    aint[nod].sst = aint[nod<<1].sst;
    aint[nod].sdr = aint[nod<<1|1].sdr;
    if(aint[nod<<1].sst == aint[nod<<1].sdr && aint[nod<<1].sst != 0)
        aint[nod].sst = aint[nod<<1].sst + aint[nod<<1|1].sst;
    if(aint[nod<<1|1].sdr == aint[nod<<1|1].sst && aint[nod<<1|1].sst != 0)
        aint[nod].sdr = aint[nod<<1|1].sdr + aint[nod<<1].sdr;
}

void update(int nod, int st, int dr, int a, int b, int val){
    updatelazy(nod, st, dr);
    if(dr < a || st > b)
        return;
    if(a <= st && b >= dr){
        flag[nod] = val;
        updatelazy(nod, st, dr);
        return;
    }

    int mid = (st + dr) / 2;

    if(st == dr)
        return;

    update(nod<<1, st, mid, a, b, val);
    update(nod<<1|1, mid + 1, dr, a, b, val);

    updatenod(nod, st, dr);

    /*aint[nod].smij = max(max(aint[2 * nod].smij, aint[2 * nod + 1].smij), aint[2 * nod].sdr + aint[2 * nod + 1].sst);

    if(aint[2 * nod].complet)
        aint[nod].sst = aint[2 * nod].sst + aint[2 * nod + 1].sst;
    else
        aint[nod].sst = aint[2 * nod].sst;

    if(aint[2 * nod + 1].complet)
        aint[nod].sdr = aint[2 * nod].sdr + aint[2 * nod + 1].sdr;
    else
        aint[nod].sdr = aint[2 * nod + 1].sdr;

    if(aint[nod].sst == aint[nod].sdr && aint[nod].sst != 0)
        aint[nod].complet = 1;
    else
        aint[nod].complet = 0;
        */
}

int main()
{
    f>>n>>m;
    update(1, 1, n, 1, n, 1);
    for(int i = 1; i <= m; ++ i){
        f>>tip;
        if(tip == 1){
            f>>x>>y;
            update(1, 1, n, x, x + y - 1, -1);
        }
        if(tip == 2){
            f>>x>>y;
            update(1, 1, n, x, x + y - 1, 1);
        }
        if(tip == 3){
            //query(1, 1, n);
            g<<max(max(aint[1].smij, aint[1].sst), aint[1].sdr)<<'\n';
        }
    }
    return 0;
}