Cod sursa(job #543271)

Utilizator DraStiKDragos Oprica DraStiK Data 27 februarie 2011 20:09:28
Problema Walls Scor 20
Compilator cpp Status done
Runda RMMS Sim Marime 2.73 kb
#include <algorithm>
#include <map>
using namespace std;

#define mp make_pair

#define DIM 200005

int W[DIM],H[DIM],aint_val[DIM<<2],aint_poz[DIM<<2];
map <pair <int,int>,int> hit;
int N,M,aint_max,aint_ind;
long long dOX[DIM];

void update (int nod,int st,int dr,int poz,int val)
{
    int mij;

    if (st==dr)
    {
        aint_val[nod]=val;
        aint_poz[nod]=st;
    }
    else
    {
        mij=(st+dr)>>1;
        if (poz<=mij)
            update (nod<<1,st,mij,poz,val);
        if (mij<poz)
            update ((nod<<1)|1,mij+1,dr,poz,val);
        if (aint_val[nod<<1]>aint_val[(nod<<1)|1])
        {
            aint_val[nod]=aint_val[nod<<1];
            aint_poz[nod]=aint_poz[nod<<1];
        }
        else
        {
            aint_val[nod]=aint_val[(nod<<1)|1];
            aint_poz[nod]=aint_poz[(nod<<1)|1];
        }
    }
}

void query (int nod,int st,int dr,int in,int sf)
{
    int mij;

    if (in<=st && dr<=sf)
    {
        if (aint_val[nod]>aint_max)
        {
            aint_max=aint_val[nod];
            aint_ind=aint_poz[nod];
        }
    }
    else
    {
        mij=(st+dr)>>1;
        if (in<=mij)
            query (nod<<1,st,mij,in,sf);
        if (mij<sf)
            query ((nod<<1)|1,mij+1,dr,in,sf);
    }
}

void read ()
{
    int i;

    dOX[0]=-1;
    scanf ("%d",&N);
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&W[i],&H[i]);
        dOX[i]=dOX[i-1]+W[i]+1;
        update (1,1,N,i,H[i]);
    }
}

int cbin (long long val)
{
    int i,step;

    for (step=1; step<=N; step<<=1);

    for (i=0; step; step>>=1)
        if (i+step<=N && dOX[i+step]<=val)
            i+=step;

    return i;
}

void solve ()
{
    int i,h,st,dr,mij,sol;
    long long w;

    scanf ("%d",&M);
    for (i=1; i<=M; ++i)
    {
        sol=0;
        scanf ("%lld%d",&w,&h);
        for (st=1, dr=cbin (w); st<=dr; )
        {
            mij=(st+dr)>>1;
            aint_max=aint_ind=0; query (1,1,N,mij,dr);

            if (aint_max>=h)
            {
                sol=aint_ind;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        if (!sol)
            printf ("MISS\n");
        else
        {
            if (++hit[mp (sol,h)]==W[sol])
            {
                printf ("HIT %lld %d YES\n",dOX[sol]-hit[mp (sol,h)]+1,sol);
                H[sol]=0;
                update (1,1,N,sol,H[sol]);
            }
            else
                printf ("HIT %lld %d NO\n",dOX[sol]-hit[mp (sol,h)]+1,sol);
        }
    }
}

int main ()
{
    freopen ("walls.in","r",stdin);
    freopen ("walls.out","w",stdout);

    read ();
    solve ();

    return 0;
}