Pagini recente » Cod sursa (job #54550) | Cod sursa (job #1072111) | Cod sursa (job #2644925) | Cod sursa (job #1146969) | Cod sursa (job #2596519)
#include <bits/stdc++.h>
using namespace std;
ifstream f("hotel.in");
ofstream g("hotel.out");
int n, p;
int a, b;
struct node
{
int lazy, length, l, r, m;
} arb[4 * 100005];
void build(int nod, int st, int dr)
{
if(st == dr)
{
arb[nod].length = arb[nod].l = arb[nod].r = arb[nod].m = 1;
arb[nod].lazy = 0;
return;
}
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
arb[nod].length = arb[2 * nod].length + arb[2 * nod + 1].length;
arb[nod].l = arb[2 * nod].length + arb[2 * nod + 1].length;
arb[nod].r = arb[2 * nod].length + arb[2 * nod + 1].length;
arb[nod].m = max(arb[nod].m, arb[2 * nod].length + arb[2 * nod + 1].length);
}
void add(int nod, int st, int dr,int val)
{
if(arb[nod].lazy)
{
arb[nod].m += (dr - st + 1) * arb[nod].lazy;
arb[nod].l += (dr - st + 1) * arb[nod].lazy;
arb[nod].r += (dr - st + 1) * arb[nod].lazy;
if(st != dr)
{
arb[2 * nod].lazy += arb[nod].lazy;
arb[2 * nod + 1].lazy += arb[nod].lazy;
}
arb[nod].lazy = 0;
}
if(st > dr || st > b || dr < a)
return;
if(a <= st && dr <= b)
{
arb[nod].m += (dr - st + 1) * val;
arb[nod].l += (dr - st + 1) * val;
arb[nod].r += (dr - st + 1) * val;
if(st != dr)
{
arb[2 * nod].lazy += val;
arb[2 * nod + 1].lazy += val;
}
return;
}
int mid = (st + dr) / 2;
add(2 * nod, st, mid, val);
add(2 * nod + 1, mid + 1, dr, val);
arb[nod].m = max(arb[2 * nod].r + arb[2 * nod + 1].l, max(arb[2 * nod].m, arb[2 * nod + 1].m));
arb[nod].l = arb[2 * nod].l;
arb[nod].r = arb[2 * nod + 1].r;
if(arb[2 * nod].l == arb[2 * nod].length)
{
arb[nod].m = max(arb[nod].m, arb[2 * nod].length + arb[2 * nod + 1].l);
arb[nod].l = arb[2 * nod].length + arb[2 * nod + 1].l;
}
if(arb[2 * nod + 1].r == arb[2 * nod + 1].length)
{
arb[nod].m = max(arb[nod].m, arb[2 * nod + 1].length + arb[2 * nod].r);
arb[nod].r = arb[2 * nod + 1].length + arb[2 * nod].r;
}
}
void Read()
{
f>>n>>p;
build(1, 1, n);
int x, y, z;
for(int i = 1;i <= p;++i)
{
f>>x;
if(x == 3)
g<<arb[1].m<<'\n';
else
{
f>>y>>z;
a = y;
b = y + z - 1;
if(x == 1)
add(1, 1, n, -1);
else
add(1, 1, n, 1);
}
}
}
int main()
{
Read();
return 0;
}