Pagini recente » Cod sursa (job #1712141) | Cod sursa (job #1043111) | Cod sursa (job #1138526) | Cod sursa (job #1583334) | Cod sursa (job #1969098)
#include<fstream>
#include<iostream>
#define DIM 100005
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
int n, m, op, a, b;
struct arb{
int smax;
int sst;
int sdr;
} A[4 * DIM];
void build( int nod, int st, int dr ){
if( st > dr )
return;
if( st == dr ){
A[nod].sst = A[nod].sdr = A[nod].smax = 1;
}else{
int mid = ( st + dr ) / 2;
build( (nod<<1), st, mid );
build( ( (nod<<1) | 1 ), mid + 1, dr );
A[nod].smax = A[nod].sst = A[nod].sdr = dr - st + 1;
}
return;
}
void update( int nod, int st, int dr, int a, int b, int val ){
if( st > dr ){
return;
}
if( a <= st && dr <= b ){
if( val == -1 ){
A[nod].smax = A[nod].sst = A[nod].sdr = 0;
}else{
A[nod].smax = A[nod].sst = A[nod].sdr = dr - st + 1;
}
}else{
int mid = ( st + dr ) / 2;
//lazy
if( A[nod].smax == 0 ){
A[(nod<<1)].smax = A[(nod<<1)].sst = A[(nod<<1)].sdr = 0;
A[(nod<<1)|1].smax = A[(nod<<1)|1].sst = A[(nod<<1)|1].sdr = 0;
}
if( A[nod].smax == dr - st + 1 ){
A[(nod<<1)].smax = A[(nod<<1)].sst = A[(nod<<1)].sdr = mid - st + 1;
A[(nod<<1)|1].smax = A[(nod<<1)|1].sst = A[(nod<<1)|1].sdr = dr - mid;
}
if( a <= mid )
update( (nod<<1), st, mid, a, b, val );
if( b > mid )
update( ((nod<<1)|1), mid + 1, dr, a, b, val );
A[nod].smax = max( max( A[(nod<<1)].smax, A[((nod<<1)|1)].smax ), A[(nod<<1)].sdr + A[((nod<<1)|1)].sst );
A[nod].sst = A[(nod<<1)].sst;
if( A[(nod<<1)].sst == mid - st + 1 ){
A[nod].sst += A[(nod<<1)|1].sst;
}
A[nod].sdr = A[(nod<<1)|1].sdr;
if( A[(nod<<1)|1].sdr == dr - mid ){
A[nod].sdr += A[(nod<<1)].sdr;
}
}
return;
}
int main(){
fin >> n >> m;
build( 1, 1, n );
for( int t = 1; t <= m; t++ ){
fin >> op;
if( op == 3 ){
fout << A[1].smax << "\n";
}else{
int x, y;
fin >> x >> y;
if( op == 1 ){
update( 1, 1, n, x, x + y - 1, -1 );
}else{
update( 1, 1, n, x, x + y - 1, 1 );
}
}
}
return 0;
}