Cod sursa(job #2805725)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 21 noiembrie 2021 20:26:16
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
//stiu ca trebuie lazy
#include <iostream>
#include <fstream>
using namespace std;

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

const int maxN = 1e5;

struct arbore {
    int st, dr, val;
} arb[maxN];

void combine (int node) {
    int fiu1 = node*2, fiu2 = node*2+1;
    if(arb[fiu1].dr + 1 == arb[fiu2].st) {
        arb[node].st = arb[fiu1].st;
        arb[node].dr = arb[fiu2].dr;
        arb[node].val = arb[fiu1].val + arb[fiu2].val;
        return ;
    }
    if(arb[fiu1].val > arb[fiu2].val)
        arb[node] = arb[fiu1];
    else
        arb[node] = arb[fiu2];

}

void build (int node, int st, int dr) {
    if(st > dr) return ;
    if(st == dr) {
        arb[node].st = arb[node].dr = st;
        arb[node].val = 1;
    } else {
        int mij = (st + dr) / 2;

        build(node * 2, st, mij);
        build(node * 2 + 1, mij+1, dr);

        combine(node);
    }
}

void update (int node, int st, int dr, int poz, int op) {
    if(st > dr) return ;
    if(st == dr) {
        if(op == 1)
            arb[node].st = arb[node].dr = -1, arb[node].val = 0;
        else
            arb[node].st = arb[node].dr = st, arb[node].val = 1;
    } else {
        int mij = (st + dr) / 2;
        if(poz <= mij) update(node * 2, st, mij, poz, op);
        else update(node * 2 + 1, mij+1, dr, poz, op);

        combine(node);
    }
}

int main()
{
    int n, p; fin >> n >> p;

    build (1, 1, n);

    for(int i = 1; i <= p; ++i) {
        int op; fin >> op;
        if(op == 1) {
            int poz, m; fin >> poz >> m;
            for(int j = poz; j < poz+m; ++j)
                update(1, 1, n, j, 1);
        } else if(op == 2) {
            int poz, m; fin >> poz >> m;
            for(int j = poz; j < poz+m; ++j)
                update(1, 1, n, j, 2);
        } else {
            fout << arb[1].dr - arb[1].st + 1<< '\n';
        }
    }
    return 0;
}