Cod sursa(job #1969098)

Utilizator robx12lnLinca Robert robx12ln Data 18 aprilie 2017 11:46:27
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#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;
}