Cod sursa(job #554542)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 14 martie 2011 22:14:06
Problema Walls Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <map>
#define Nmax 100005
#define mp make_pair
using namespace std;

map< pair<int,int> , int > Damage;
int A[Nmax*4],Wh[Nmax*4];
int W[Nmax],X[Nmax];
int N,M,care_zid;

inline void Update(int nod,int l,int r,int poz,int val){
    if( l==r ){
        A[nod]=val;
        Wh[nod]=poz;
        return;
    }
    int m=l+(r-l)/2;
    if( poz<=m ) Update(2*nod,l,m,poz,val);
    else Update(2*nod+1,m+1,r,poz,val);
    if( A[2*nod] > A[2*nod+1] ) A[nod]=A[2*nod], Wh[nod]=Wh[2*nod];
    else A[nod]=A[2*nod+1], Wh[nod]=Wh[2*nod+1];
}

inline void Query(int nod,int l,int r,int x,int y,int val){
    if( l>r || A[nod]<val ) return;
    if( x<=l && r<=y ) care_zid=Wh[nod];

    int m=l+(r-l)/2;
    if( A[2*nod+1] >= val && m<y )
        Query(2*nod+1,m+1,r,x,y,val);
    else
    if( A[2*nod]>= val && x<=m)
        Query(2*nod,l,m,x,y,val);
}

inline int caut_bin(int l,int r,int x){
    int m,ret=0;
    while(l<=r){
        m=l+(r-l)/2;
        if( X[m]<=x ) ret=m, l=m+1;
        else r=m-1;
    }
    return ret;
}

int main(){
    int i,h,x,y,lim,damage;
    freopen("walls.in","r",stdin);
    freopen("walls.out","w",stdout);
    scanf("%d",&N);

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

    scanf("%d",&M);
    for(i=1;i<=M;++i){
        scanf("%d%d",&x,&y);
        care_zid=0;
        lim=caut_bin(1,N,x);
        Query(1,1,N,1,lim,y);

        if( care_zid ){
            damage=++Damage[ mp( care_zid,y ) ];

            printf("HIT %d %d ",X[care_zid]-damage+1,care_zid);
            if( damage == W[care_zid] ){
                Update(1,1,N,care_zid,y-1);
                Damage[mp(care_zid,y)]=0;
                printf("YES\n");
            }
            else
                printf("NO\n");
        }
        else printf("MISS\n");
    }

    fclose(stdin); fclose(stdout);
    return 0;
}