Cod sursa(job #1240629)

Utilizator teoionescuIonescu Teodor teoionescu Data 11 octombrie 2014 19:47:40
Problema Walls Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("walls.in");
ofstream out("walls.out");
const int Nmax = 100001;
const int Wmax = 2000000001;
int N,M;
int W[Nmax],H[Nmax];
ll E[Nmax];
int find(ll x){
    int i=0,pas=1<<20;
    while(pas){
        if(i+pas<=N && E[i+pas]<x) i+=pas;
        pas>>=1;
    }
    return i;
}
int A[20*Nmax];
int Query(int i,int st,int dr,int a,int b){
    if(a<=st && dr<=b) return A[i];
    int mij=(st+dr)/2;
    if(b<=mij) return Query(2*i,st,mij,a,b);
    if(a>mij) return Query(2*i+1,mij+1,dr,a,b);
    return max( Query(2*i,st,mij,a,mij) , Query(2*i+1,mij+1,dr,mij+1,b) );
}
void Update(int i,int st,int dr,int &w,int &val){
    if(st>=dr) A[i]=val;
    else{
        int mij=(st+dr)/2;
        if(w<=mij) Update(2*i,st,mij,w,val);
        else Update(2*i+1,mij+1,dr,w,val);
        A[i]=max(A[2*i],A[2*i+1]);
    }
}
int query(int a,int b){
    if(a<1) a=1;
    if(b<1) b=1;
    if(a>N) a=N;
    if(b>N) b=N;
    return Query(1,1,N,a,b);
}
int update(int pos,int val){
    Update(1,1,N,pos,val);
}
int find_hit(int e,int h){
    e++;
    int i=e,pas=1<<20;
    while(pas){
        if( query(i-pas,e-1)<h ) i-=pas;
        pas>>=1;
    }
    return i-1;
}
struct hash{
    hash* next;
    int x,h,many;
};
const int MOD = 666013;
hash* map[MOD];
int affect(int pos,int h){
    int idx = ( 1LL*h*h + pos ) % MOD;
    hash *p=map[idx],*f=NULL;
    while(p){
        if(p->x=pos && p->h==h) f=p;
        p=p->next;
    }
    if(f) f->many++;
    else{
        f=new hash;
        f->x=pos;
        f->h=h;
        f->many=1;
        f->next=map[idx];
        map[idx]=f;
    }
    if(f->many==W[f->x]){
        f->many=0;
        return W[f->x];
    }
    return f->many;
}
int main(){
    in>>N;
    E[0]=-1;
    for(int i=1;i<=N;i++){
        in>>W[i]>>H[i];
        E[i]=E[i-1]+W[i]+1;
        update(i,H[i]);
    }
    in>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        int hit=find_hit(find(x),y);
        if(hit<1) out<<"MISS\n";
        else{
            int depth=affect(hit,y);
            if(depth==W[hit]){
                H[hit]-- , update(hit,H[hit]);
            }
            out<<"HIT "<<E[hit]-depth+1<<" "<<hit<<" "<<(depth==W[hit]?"YES\n":"NO\n");
        }
    }
    return 0;
}