Cod sursa(job #762167)

Utilizator gicu_01porcescu gicu gicu_01 Data 28 iunie 2012 23:42:20
Problema Hotel Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
int n,m;

struct arb
{
    int cam;
    int x;
    int y;
} arbori[200001];

void update(int nod,int i,int j,int a,int b,int val)
{
    if (i==j)
    {
        arbori[nod].cam=val;
        if (val==1)
        {
            arbori[nod].x=i;
            arbori[nod].y=j;
            return;
        } else
        {
            arbori[nod].x=0;
            arbori[nod].y=0;
            return;
        }
    }
    int p=(i+j)/2;
    if (a<=p) update(nod*2,i,p,a,b,val);
    if (p<b) update(nod*2+1,p+1,j,a,b,val);
    if (arbori[nod*2+1].x-arbori[nod*2].y==1)
    {
        arbori[nod].cam=arbori[nod*2].cam+arbori[nod*2+1].cam;
        arbori[nod].x=arbori[nod*2].x;
        arbori[nod].y=arbori[nod*2+1].y;
    }else
    if (arbori[nod*2].cam>arbori[nod*2+1].cam)
    {
        arbori[nod].cam=arbori[nod*2].cam;
        arbori[nod].x=arbori[nod*2].x;
        arbori[nod].y=arbori[nod*2].y;
    } else
    {
        arbori[nod].cam=arbori[nod*2+1].cam;
        arbori[nod].x=arbori[nod*2+1].x;
        arbori[nod].y=arbori[nod*2+1].y;
    }

}


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