Cod sursa(job #543739)

Utilizator DraStiKDragos Oprica DraStiK Data 28 februarie 2011 15:52:31
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <algorithm>
#include <map>
using namespace std;

#define mp make_pair

#define DIM 100005

map <pair <int,int>,int> hit;
int W[DIM],aint[DIM<<2];
long long dOX[DIM];
int N,M;

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

    if (st==dr)
        aint[nod]=val;
    else
    {
        mij=(st+dr)>>1;

        if (poz<=mij)
            update (nod<<1,st,mij,poz,val);
        else
            update ((nod<<1)|1,mij+1,dr,poz,val);

        aint[nod]=max (aint[nod<<1],aint[(nod<<1)|1]);
    }
}

int query (int nod,int st,int dr,long long x,int y)
{
    int mij,poz;

    if (x<dOX[st] || aint[nod]<y)
        return 0;

    if (st==dr)
        return st;

    mij=(st+dr)>>1;
    poz=query ((nod<<1)|1,mij+1,dr,x,y);
    if (!poz)
        poz=query (nod<<1,st,mij,x,y);

    return poz;
}

void read ()
{
    int i,h;

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

void solve ()
{
    long long x;
    int i,poz,y;

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

        poz=query (1,1,N,x,y);
        if (poz)
        {
            if (++hit[mp (poz,y)]==W[poz])
            {
                printf ("HIT %lld %d YES\n",dOX[poz]+W[poz]-hit[mp (poz,y)],poz);
                update (1,1,N,poz,y-1);
            }
            else
                printf ("HIT %lld %d NO\n",dOX[poz]+W[poz]-hit[mp (poz,y)],poz);
        }
        else
            printf ("MISS\n");
    }
}

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

    read ();
    solve ();

    return 0;
}