Cod sursa(job #543293)

Utilizator DraStiKDragos Oprica DraStiK Data 27 februarie 2011 20:35:34
Problema Walls Scor 10
Compilator cpp Status done
Runda RMMS Sim Marime 1.87 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define sc second
#define fs first

#define DIM 200005

vector <pair <long long,long long> > hit[DIM];
long long pOX[DIM],w[DIM],h[DIM];
long long N,M;

void read ()
{
    long long i;

    scanf ("%lld",&N);

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

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

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

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

    return i;
}

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

    scanf ("%lld",&M);
    for (i=1; i<=M; ++i)
    {
        scanf ("%lld%lld",&x,&y);

        start=cbin (x); nohit=1;
        for (j=start; j>=1; --j)
            if (h[j]>=y)
            {
                dmg=0;
                for (it=hit[j].begin (); it!=hit[j].end (); ++it)
                    if (it->fs==y)
                    {
                        dmg=it->sc;
                        ++it->fs;
                        break ;
                    }

                if (!dmg)
                    hit[j].pb (mp (y,1));

                if (!(w[j]-dmg-1))
                {
                    printf ("HIT %lld %lld YES\n",pOX[j]-dmg,j);
                    h[j]=y-1;
                }
                else
                    printf ("HIT %lld %lld 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;
}