Cod sursa(job #2466240)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 1 octombrie 2019 19:30:47
Problema Hotel Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>

using namespace std;
ifstream f("hotel.in");
ofstream g("hotel.out");
struct meme{
    int laiz;
    int val, st, dr;
}ait[100001];
int i, n, m, op, st, lung, val;
void update(int node, int a, int b, int x, int y, int val){
    int mid = (a + b) / 2;
    if(ait[node].laiz != 0 && a != b){
        update(2 * node, a, mid, a, mid, ait[node].laiz);
        update(2 * node + 1, mid + 1, b, mid + 1, b, ait[node].laiz);
        ait[node].laiz = 0;
    }
    if(x <= a && b <= y){
        ait[node].laiz = val;
        ait[node].val += val * (b - a + 1);
        ait[node].st += val * (b - a + 1);
        ait[node].dr += val * (b - a + 1);
        return;
    }
    if(mid >= x)
        update(2 * node, a, mid, x, y, val);
    if(mid + 1 <= y)
        update(2 * node + 1, mid + 1, b, x, y, val);
    ait[node].val = max(ait[2 * node].val, ait[2 * node + 1].val);
    ait[node].val = max(ait[node].val, ait[2 * node].dr + ait[2 * node + 1].st);
    ait[node].st = ait[2 * node].st;
    if(ait[2 * node].st == mid - a + 1)
        ait[node].st += ait[2 * node + 1].st;
    ait[node].dr = ait[2 * node + 1].dr;
    if(ait[2 * node + 1].dr == b - mid)
        ait[node].dr += ait[2 * node].dr;
}
int main()
{   f >> n >> m;
    for(i = 1; i <= n; i++)
        update(1, 1, n, i, i, 1);
    for(i = 1; i <= m; i++){
        f >> op;
        if(op == 1 || op == 2){
            f >> st >> lung;
            val = -1;
            if(op == 2)
                val = 1;
            update(1, 1, n, st, st + lung - 1, val);
        }
        else
            g << ait[1].val << '\n';
    }

    return 0;
}