Cod sursa(job #82365)
#include <cstdio>
const int maxi = 2 << 17;
FILE *in = fopen("hotel.in","r"), *out = fopen("hotel.out","w");
int n, m;
int A[maxi];
int B[maxi];
int C[maxi];
void build(int nod, int st, int dr)
{
if ( st == dr )
{
A[nod] = 1;
B[nod] = C[nod] = st;
return;
}
int q = nod << 1;
int m = (st + dr) >> 1;
build(q, st, m);
build(q+1, m+1, dr);
A[nod] = A[q] + A[q+1];
B[nod] = B[q];
C[nod] = C[q+1];
}
int op;
int X, Y;
void update(int nod, int st, int dr)
{
if ( st > Y || dr < X )
return;
if ( X <= st && dr <= Y )
{
if ( op == 2 )
A[nod] = dr - st + 1, B[nod] = st, C[nod] = dr;
else
A[nod] = 0, B[nod] = 0, C[nod] = 0;
// return;
}
if ( st == dr )
return;
int q = nod << 1;
int m = (st + dr) >> 1;
update(q, st, m);
update(q+1, m+1, dr);
if ( C[q] + 1 == B[q+1] )
{
A[nod] = A[q] + A[q+1];
B[nod] = B[q];
C[nod] = C[q+1];
}
else
{
if ( A[q] > A[q+1] )
{
A[nod] = A[q];
B[nod] = B[q];
C[nod] = C[q];
}
else
{
A[nod] = A[q+1];
B[nod] = B[q+1];
C[nod] = C[q+1];
}
}
}
int main()
{
fscanf(in, "%d %d", &n, &m);
build(1, 1, n);
int a, b, c;
for ( int i = 0; i < m; ++i )
{
fscanf(in, "%d", &a);
if ( a == 3 )
fprintf(out, "%d\n", A[1]);
else
{
fscanf(in, "%d %d", &b, &c);
op = a;
X = b;
Y = b + c - 1;
update(1, 1, n);
}
}
return 0;
}