Cod sursa(job #2811603)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 2 decembrie 2021 18:20:31
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>

#define MAX_N 100000

struct nodeAINT {
    int maxim, maximLeft, maximRight, lazy;
};

int max( int a, int b ) {
    return a > b ? a : b;
}

struct AINT {
    nodeAINT aint[4 * MAX_N];

    void init( int nod, int l, int r ) {
        int mid = (l + r) / 2;

        aint[nod].lazy = 0;
        aint[nod].maxim = aint[nod].maximLeft = aint[nod].maximRight = r - l + 1;

        if ( l == r )
            return;

        init( nod * 2 + 1, l, mid );
        init( nod * 2 + 2, mid + 1, r );

    }

    void update( int nod, int l, int r, int lu, int ru, int tip ) {
        int mid = (l + r) / 2;

        if ( l > r )
            return;
        if ( aint[nod].lazy > 0 ) {
            if ( l != r )
                aint[nod * 2 + 1].lazy = aint[nod * 2 + 2].lazy = aint[nod].lazy;
            aint[nod].lazy = 0;
            aint[nod].maxim = aint[nod].maximLeft = aint[nod].maximRight = (r - l + 1) * aint[nod].lazy;
        }

        if ( lu > r || ru < l )
            return;

        if ( lu <= l && r <= ru ) {
            aint[nod].lazy = 0;
            if ( l != r )
                aint[nod * 2 + 1].lazy = aint[nod * 2 + 2].lazy = tip;
            aint[nod].maxim = aint[nod].maximLeft = aint[nod].maximRight = (r - l + 1) * (tip == 1 ? 0 : 1);

            return;
        }

        if ( l != r ) {
            update( nod * 2 + 1, l, mid, lu, ru, tip );
            update( nod * 2 + 2, mid + 1, r, lu, ru, tip );

            aint[nod].maximLeft = aint[nod * 2 + 1].maximLeft;
            if ( aint[nod * 2 + 1].maximLeft == mid - l + 1 )
                aint[nod].maximLeft += aint[nod * 2 + 2].maximLeft;

            aint[nod].maximRight = aint[nod * 2 + 2].maximRight;
            if ( aint[nod * 2 + 2].maximRight == r - mid )
                aint[nod].maximRight += aint[nod * 2 + 1].maximRight;

            aint[nod].maxim = max( max( aint[nod * 2 + 1].maxim, aint[nod * 2 + 2].maxim ), aint[nod * 2 + 1].maximRight + aint[nod * 2 + 2].maximLeft );
        }
    }
    int query() {
        return aint[0].maxim;
    }
};

AINT hotel;


int main() {
    FILE *fin, *fout;
    int n, q, tip, l, r, len, i;

    fin = fopen( "hotel.in", "r" );
    fout = fopen( "hotel.out", "w" );

    fscanf( fin, "%d%d", &n, &q );

    hotel.init( 0, 0, n - 1 );

    for ( i = 0; i < q; i++ ) {
        fscanf( fin, "%d", &tip );

        if ( tip == 3 )
            fprintf( fout, "%d\n", hotel.query() );
        else {
            fscanf( fin, "%d%d", &l, &len );
            l--;
            r = l + len - 1;
            hotel.update( 0, 0, n - 1, l, r, tip );
        }
    }

    fclose( fin );
    fclose( fout );

    return 0;
}