Cod sursa(job #2339744)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 9 februarie 2019 11:23:29
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>

#define MAXN 100000

using namespace std;

ifstream fin ( "hotel.in" );
ofstream fout ( "hotel.out" );

struct Node {
    int slm;
    int pref;
    int suf;
    int lazy;

    Node( ) {
        ;
    }

    Node ( int val ) {
        slm = pref = suf = val;
    }
};

Node aint[4 * MAXN + 5];

void propagate ( int poz, int st, int dr ) {
    if ( aint[poz].lazy == -1 )
        return;

    int mid = ( st + dr ) / 2;

    if ( aint[poz].lazy == 1 ) {
        aint[2 * poz] = Node ( 0 );
        aint[2 * poz + 1] = Node ( 0 );
    } else {
        aint[2 * poz] = Node ( mid - st + 1 );
        aint[2 * poz + 1] = Node ( dr - mid );
    }

    aint[2 * poz].lazy = aint[2 * poz + 1].lazy = aint[poz].lazy;

    aint[poz].lazy = -1;
}

Node merge ( int st, int dr, Node a, Node b ) {
    int mid = ( st + dr ) / 2;

    Node aux;

    aux.pref = a.pref;
    aux.suf = b.suf;

    if ( a.pref == mid - st + 1 )
        aux.pref += b.pref;

    if ( b.suf == dr - mid )
        aux.suf += a.suf;

    aux.slm = max ( max ( max ( a.slm, b.slm ), max ( aux.pref, aux.suf ) ), a.suf + b.pref );

    aux.lazy = -1;

    return aux;
}

void update ( int a, int b, int val, int poz, int st, int dr ) {
    if ( b < st || dr < a )
        return;

    if ( a <= st && dr <= b ) {
        if ( val == 1 )
            aint[poz] = Node ( 0 );
        else
            aint[poz] = Node ( dr - st + 1 );

        aint[poz].lazy = val;
    } else {
        int mid = ( st + dr ) / 2;

        propagate ( poz, st, dr );

        update ( a, b, val, 2 * poz, st, mid );
        update ( a, b, val, 2 * poz + 1, mid + 1, dr );

        aint[poz] = merge ( st, dr, aint[2 * poz], aint[2 * poz + 1] );
    }
}

int main() {
    int n, m;

    fin >> n >> m;

    update ( 1, n, 0, 1, 1, n );

    for ( int i = 1; i <= m; i++ ) {
        int op;

        fin >> op;

        if ( op == 3 )
            fout << aint[1].slm << '\n';
        else {
            int a, b;

            fin >> a >> b;

            if ( op == 1 )
                update ( a, a + b - 1, 1, 1, 1, n );
            else
                update ( a, a + b - 1, 0, 1, 1, n );
        }
    }

    return 0;
}