Pagini recente » Cod sursa (job #1607885) | Cod sursa (job #1217327) | Cod sursa (job #65977) | Cod sursa (job #3183750) | Cod sursa (job #331154)
Cod sursa(job #331154)
#include <stdio.h>
#define dim 1<<19
struct snode {
int left, right, all;
};
int n, p;
int op, start, end;
snode arb[dim];
int max(const int &a, const int &b) {
return a>b?a:b;
}
void init(int node, int l, int r) {
arb[node].left=arb[node].right=arb[node].all=r-l+1;
if (l==r) return;
int m=(l+r)/2;
init(node*2, l, m);
init(node*2+1, m+1, r);
}
void update(int node, int l, int r) {
int val;
if (start<=l && r<=end) {
if (op) val=r-l+1;
else val=0;
arb[node].left=arb[node].right=arb[node].all=val;
return;
}
int m=(l+r)/2, rnode=node*2+1, lnode=node*2;
if (arb[node].all==r-l+1) {
arb[lnode].left=arb[lnode].right=arb[lnode].all=m-l+1;
arb[rnode].left=arb[rnode].right=arb[rnode].all=r-m;
}
if (!arb[node].all) {
arb[lnode].left=arb[lnode].right=arb[lnode].all=0;
arb[rnode].left=arb[rnode].right=arb[rnode].all=0;
}
if (start<=m) update(lnode, l, m);
if (m<end) update(rnode, m+1, r);
arb[node].left=arb[lnode].left;
arb[node].right=arb[rnode].right;
arb[node].all=max(arb[lnode].all, arb[rnode].all);
arb[node].all=max(arb[node].all, arb[lnode].right+arb[rnode].left);
if (arb[node].left==m-l+1) arb[node].left+=arb[rnode].left;
if (arb[node].right==r-m) arb[node].right+=arb[lnode].right;
}
int main() {
freopen("hotel.in", "r", stdin);
freopen("hotel.out", "w", stdout);
scanf("%d %d\n", &n, &p);
init(1, 1, n);
for (; p; --p) {
scanf("%d ", &op);
if (op==3) {
printf("%d\n", arb[1].all);
continue;
}
--op;
scanf("%d %d\n", &start, &end);
end=start+end-1;
update(1, 1, n);
}
return 0;
}