Pagini recente » Cod sursa (job #2219449) | Cod sursa (job #2830453) | Cod sursa (job #2207908) | Cod sursa (job #1117483) | Cod sursa (job #1911232)
#include <iostream>
#include <cstdio>
using namespace std;
#define DIM 400000
struct elem {
int mx;
int lf;
int rg;
} arbint[DIM];
int N, M;
void update(int nod, int st, int dr, int a, int b, int tip) {
if(a <= st && dr <= b) {
if(tip == 1) {
arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = 0;
}
else {
arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = dr - st + 1;
}
return ;
}
int mij = (st + dr) / 2;
if(arbint[nod].mx == 0) {
arbint[2 * nod].mx = arbint[2 * nod].lf = arbint[2 * nod].rg = 0;
arbint[2 * nod + 1].mx = arbint[2 * nod + 1].lf = arbint[2 * nod + 1].rg = 0;
}
if(arbint[nod].mx == dr - st + 1) {
arbint[2 * nod].mx = arbint[2 * nod].lf = arbint[2 * nod].rg = mij - st + 1;
arbint[2 * nod + 1].mx = arbint[2 * nod + 1].lf = arbint[2 * nod + 1].rg = dr - mij;
}
if(b > mij) {
update(2 * nod + 1, mij + 1, dr, a, b, tip);
}
if(a <= mij) {
update(2 * nod, st, mij, a, b, tip);
}
arbint[nod].mx = max(arbint[2 * nod].mx, max(arbint[2 * nod + 1].mx, arbint[2 * nod].rg + arbint[2 * nod + 1].lf));
arbint[nod].lf = arbint[2 * nod].lf;
if(arbint[nod].lf == mij - st + 1) {
arbint[nod].lf += arbint[2 * nod + 1].lf;
}
arbint[nod].rg = arbint[2 * nod + 1].rg;
if(arbint[nod].rg == dr - mij) {
arbint[nod].rg += arbint[2 * nod].rg;
}
}
void buildArb(int nod, int st, int dr) {
if(st == dr) {
arbint[nod].mx = arbint[nod].lf = arbint[nod].rg = 1;
return ;
}
int mij = (st + dr) / 2;
buildArb(2 * nod, st, mij);
buildArb(2 * nod + 1, mij + 1, dr);
arbint[nod].mx = dr - st + 1;
arbint[nod].rg = dr - st + 1;
arbint[nod].lf = dr - st + 1;
}
int main() {
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
scanf("%d %d\n", &N, &M);
buildArb(1, 1, N);
int tip, x, y;
while(M--) {
scanf("%d", &tip);
if(tip == 3) {
cout << arbint[1].mx << '\n';
}
else {
scanf("%d %d\n", &x, &y);
update(1, 1, N, x, x + y - 1, tip);
}
}
return 0;
}