Cod sursa(job #555503)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 15 martie 2011 16:07:34
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <map>
#define Nmax 100005
#define mp make_pair
#define LL long long
using namespace std;

map< pair<int,int> , int > Damage;
int A[Nmax*4];
int W[Nmax];
LL 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;
        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);

    A[nod]=A[2*nod] > A[2*nod+1] ? A[2*nod] : A[2*nod+1];
}

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

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

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;
        Query(1,1,N,x,y);

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

            printf("HIT %lld ",X[care_zid]-damage+1);
            printf("%d ",care_zid);

            if( damage == W[care_zid] ){
                Update(1,1,N,care_zid,y-1);
                printf("YES\n");
            }
            else
                printf("NO\n");
        }
        else printf("MISS\n");
    }

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