Cod sursa(job #1768072)

Utilizator antanaAntonia Boca antana Data 30 septembrie 2016 09:39:43
Problema Hotel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.01 kb
#include <cstdio>
#include <ctype.h>
#define BUF_SIZE (1<<17)
#define MAXN 100000
#define DIM (1<<17)

char buf[BUF_SIZE], buf2[BUF_SIZE];
int pos = BUF_SIZE, pos2, n, m, l1, l2, val, suma[DIM], prefix[DIM], sufix[DIM], maxs[DIM], lazy[DIM], v[MAXN+1];

FILE *fin, *fout;

inline char getChar();
inline int getInt();
inline void putch(char);
inline void scrie(int);

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

void dfs(int st, int dr, int nod)
{
    if(st == dr){
        prefix[nod] = 1;
        sufix[nod] = 1;
        maxs[nod] = 1;
        return;
    }

    int m = (st+dr)/2;
    dfs(st, m, nod*2);
    dfs(m+1, dr, nod*2+1);

    prefix[nod] = sufix[nod] = maxs[nod] = dr-st+1;
}

inline void modifica(int st, int dr, int nod)
{
    if(lazy[nod] != 0)
    {
        suma[nod] += lazy[nod] *(dr-st+1);

        if(st!=dr){
            lazy[nod*2] += lazy[nod];
            lazy[nod*2+1] += lazy[nod];
        }
        lazy[nod] = 0;

        if(!suma[nod])
        {
            prefix[nod] = dr-st+1;
            sufix[nod] = dr-st+1;
            maxs[nod] = dr-st+1;
        }
        else
        {
            prefix[nod] = 0;
            sufix[nod] = 0;
            maxs[nod] = 0;
        }
    }
}

void update(int st, int dr, int nod)
{
    if(lazy[nod]!=0)
    {
        suma[nod] += lazy[nod] *(dr-st+1);

        if(st!=dr){
            lazy[nod*2] += lazy[nod];
            lazy[nod*2+1] += lazy[nod];
        }
        lazy[nod] = 0;

        if(!suma[nod])
        {
            prefix[nod] = dr-st+1;
            sufix[nod] = dr-st+1;
            maxs[nod] = dr-st+1;
        }
        else
        {
            prefix[nod] = 0;
            sufix[nod] = 0;
            maxs[nod] = 0;
        }
    }

    if(l1 <= st && dr <= l2)
    {
        suma[nod] += val * (dr-st+1);

        if(!suma[nod])
        {
            prefix[nod] = dr-st+1;
            sufix[nod] = dr-st+1;
            maxs[nod] = dr-st+1;
        }
        else
        {
            prefix[nod] = 0;
            sufix[nod] = 0;
            maxs[nod] = 0;
        }

        if(st != dr){
            lazy[nod*2] += val;
            lazy[nod*2+1] += val;
        }
        return;
    }
    int m = (st+dr)/2;

    if(l1 <= m) update(st, m, nod*2);
    if(l2 > m) update(m+1, dr, nod*2+1);

    modifica(st, m, nod*2);
    modifica(m+1, dr, nod*2+1);

    suma[nod] = suma[nod*2] + suma[nod*2+1];

    if(!suma[nod*2]) prefix[nod] = (m-st)+1 + prefix[nod*2+1];
    else prefix[nod] = prefix[nod*2];

    if(!suma[nod*2+1]) sufix[nod] = dr-m + sufix[nod*2];
    else sufix[nod] = sufix[nod*2+1];

    maxs[nod] = maxim(sufix[nod*2] + prefix[nod*2+1], maxim(maxs[nod*2], maxs[nod*2+1]));
}

int main()
{

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

    int i, a;

    n = getInt(); m = getInt();

    dfs(1, n, 1);

    for(i=1;i<=m;++i)
    {
        a = getInt();
        if(a == 3){
            scrie(maxs[1]);
            putch('\n');
        }
        if(a==2 || a==1)
        {
            l1 = getInt();
            l2 = getInt();
            l2 = l2 + l1 - 1;
            val = ((a==1) ? 1 : -1);
            update(1, n, 1);
        }
    }
    fwrite(buf2, 1, pos2, fout);

    fclose(fin);
    fclose(fout);

    return 0;
}

inline char getChar()
{
    if(pos == BUF_SIZE) pos=0, fread(buf, 1, BUF_SIZE, fin);
    return buf[pos++];
}

inline int getInt()
{
    int nr=0;
    char c;

    c = getChar();
    while(!isdigit(c)) c = getChar();
    while(isdigit(c))
    {
        nr = nr*10 + c-'0';
        c = getChar();
    }

    return nr;
}

inline void putch(char c)
{
    buf2[pos2++] = c;
    if(pos2 == BUF_SIZE) fwrite(buf2, 1, BUF_SIZE, fout);
}
inline void scrie(int nr)
{
    char s[10];
    int k=0;

    do{
        s[k++] = nr%10 + '0';
        nr /= 10;
    }while(nr);

    while(k)
    {
        --k;
        putch(s[k]);
    }
}