Cod sursa(job #543273)

Utilizator DraStiKDragos Oprica DraStiK Data 27 februarie 2011 20:11:47
Problema Walls Scor 20
Compilator cpp Status done
Runda RMMS Sim Marime 1.83 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 <int,int> > hit[DIM];
long long pOX[DIM];
int w[DIM],h[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;
    }
    pOX[0]=0;
}

inline 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 && pOX[i+step]<=val)
            i+=step;

    return i;
}

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

    scanf ("%d",&M);
    for (i=1; i<=M; ++i)
    {
        scanf ("%lld%d",&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 %d YES\n",pOX[j]-dmg,j);
                    h[j]=y-1;
                }
                else
                    printf ("HIT %lld %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;
}