Pagini recente » Cod sursa (job #67057) | Cod sursa (job #1860200) | Cod sursa (job #1030172) | Cod sursa (job #2043003) | Cod sursa (job #2805725)
//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;
}