Cod sursa(job #541701)

Utilizator DraStiKDragos Oprica DraStiK Data 25 februarie 2011 13:25:03
Problema Walls Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 1.77 kb
#include <algorithm>
#include <set>
using namespace std;

#define lb lower_bound
#define mp make_pair
#define sc second

#define DIM 5005

set <pair <int,int> > hit[DIM];
int w[DIM],h[DIM],pOX[DIM];
int N,M;

void read ()
{
    int i;

    scanf ("%d",&N);
    pOX[0]=-1;
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&w[i],&h[i]);
        pOX[i]=pOX[i-1]+w[i]+1;
    }
}

inline int cbin (int val)
{
    int st,dr,mij,sol;

    sol=0;
    for (st=1, dr=N; st<=dr; )
    {
        mij=(st+dr)>>1;
        if (pOX[mij]<val)
        {
            sol=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }

    return sol;
}

void solve ()
{
    set <pair <int,int> > :: iterator it;
    int i,j,x,y,start,dmg,nohit;

    scanf ("%d",&M);
    for (i=1; i<=M; ++i)
    {
        scanf ("%d%d",&x,&y);
        start=cbin (x);
        nohit=1;
        for (j=start; j>=1; --j)
            if (h[j]>=y)
            {
                it=hit[j].lb (mp (y,0));
                if (it==hit[j].end ())
                    dmg=0;
                else
                {
                    dmg=it->sc;
                    hit[j].erase (it);
                }
                hit[j].insert (mp (y,dmg+1));

                if (!(w[j]-dmg-1))
                {
                    printf ("HIT %d %d YES\n",pOX[j]-dmg,j);
                    h[i]=y-1;
                }
                else
                    printf ("HIT %d %d NO\n",pOX[j]-dmg,j);
                nohit=0;
                break ;
            }
        if (nohit)
            printf ("MISS\n");
    }
}

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

    read ();
    solve ();

    return 0;
}