Cod sursa(job #82365)

Utilizator DastasIonescu Vlad Dastas Data 6 septembrie 2007 18:38:27
Problema Hotel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#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;
}