Cod sursa(job #764085)

Utilizator gicu_01porcescu gicu gicu_01 Data 4 iulie 2012 00:35:47
Problema Hotel Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <stdio.h>
#include <stdlib.h>
int n,m,a,b;

struct x
{
    int max;
    int l_max;
    int r_max;
} arb[200001];

int max(int a,int b)
{
    if (a>=b) return a; else return b;
}

void init(int nod,int i,int j)
{
    if (i==j)
    {
        arb[nod].max=1;
        arb[nod].l_max=1;
        arb[nod].r_max=1;
        return;
    }
    int p=(i+j)/2;
    init(nod*2,i,p);
    init(nod*2+1,p+1,j);
    arb[nod].max=arb[nod].l_max=arb[nod].r_max=j-i+1;
}

void update(int nod,int i,int j,int val)
{
    if (i>=a && j<=b)
    {
        arb[nod].max=arb[nod].l_max=arb[nod].r_max=val;
        arb[nod*2].max=arb[nod*2].l_max=arb[nod*2].r_max=val;
        arb[nod*2+1].max=arb[nod*2+1].l_max=arb[nod*2+1].r_max=val;
        return;
    }
    int p=(i+j)/2;
    if (a<=p) update(nod*2,i,p,val);
    if (arb[nod].max==0) arb[nod*2+1].max=arb[nod*2+1].l_max=arb[nod*2+1].r_max=val;
    if (b>p) update(nod*2+1,p+1,j,val);
    if (arb[nod].max==0) arb[nod*2].max=arb[nod*2].l_max=arb[nod*2].r_max=val;
    if (arb[nod*2].max==p-i+1 && arb[nod*2+1].max==j-p)
    {
        arb[nod].max=arb[nod].l_max=arb[nod].r_max=j-i+1;
    }else
    if (arb[nod*2].max==p-i+1)
    {
        arb[nod].max=max(max(arb[nod*2].max,arb[nod*2+1].max),arb[nod*2].r_max+arb[nod*2+1].l_max);
        arb[nod].l_max=arb[nod*2].r_max+arb[nod*2+1].l_max;
        arb[nod].r_max=arb[nod*2+1].r_max;
    }else
    if (arb[nod*2+1].max==j-p)
    {
        arb[nod].max=max(max(arb[nod*2].max,arb[nod*2+1].max),arb[nod*2].r_max+arb[nod*2+1].l_max);
        arb[nod].l_max=arb[nod*2].l_max;
        arb[nod].r_max=arb[nod*2].r_max+arb[nod*2+1].r_max;
    }else
    {
        arb[nod].max=max(max(arb[nod*2].max,arb[nod*2+1].max),arb[nod*2].r_max+arb[nod*2+1].l_max);
        arb[nod].l_max=arb[nod*2].l_max;
        arb[nod].r_max=arb[nod*2+1].r_max;
    }
}


int main()
{
    int i,x,j,c;
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    scanf("%i%i",&n,&m);
    init(1,1,n);
    for (i=1; i<=m; i++)
    {
        scanf("%i",&x);
        if (x==1)
        {
            scanf("%i%i",&a,&c);
            b=a+c-1;
            update(1,1,n,0);
        }else
        if (x==2)
        {
            scanf("%i%i",&a,&c);
            b=a+c-1;
            update(1,1,n,1);
        }else printf("%i\n",arb[1].max);
    }
    return 0;
}