Cod sursa(job #595895)

Utilizator S7012MYPetru Trimbitas S7012MY Data 14 iunie 2011 20:13:40
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <map>
#define DN 1000005
#define DA 4*DN
#define LL long long
#define x first
#define y second
using namespace std;

typedef pair<int, int> per;
per v[DN];
int ai[DA],n,m,p,val,gls,gld;
LL poz[DN];
map<per,int> mp;

void update(int vn, int ls, int ld) {
    if(ls==ld) {
        ai[vn]=val;
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(p<=m) update(fs,ls,m);
    else update(fs+1,m+1,ld);
    ai[vn]=max(ai[fs],ai[fs+1]);
}

int query(int vn, int ls, int ld) {
    if(gls<poz[ls] || gld>ai[vn]) return 0;
    if(ls==ld) return ls;
    int ret,m=(ls+ld)>>1,fs=vn<<1;
    ret=query(fs+1,m+1,ld);
    if(0==ret) ret=query(fs,ls,m);
    return ret;
}

int main()
{
    ifstream f("walls.in");
    ofstream g("walls.out");
    f>>n;
    for(int i=1; i<=n; ++i) {
        f>>v[i].x>>v[i].y;
        p=i; val=v[i].y;
        update(1,1,n);
        poz[i]=poz[i-1]+v[i-1].x+1;
    }
    f>>m;
    for(int i=1; i<=m; ++i) {
        f>>gls>>gld;
        int sol=query(1,1,n);
        if(0==sol) g<<"MISS\n";
        else {
            g<<"HIT ";
            if(mp.find(make_pair(sol,gld))!=mp.end()) ++mp[make_pair(sol,gld)];
            else mp[make_pair(sol,gld)]=1;
            gls=poz[sol]+v[sol].x-mp[make_pair(sol,gld)];
            g<<gls<<' '<<sol<<' ';
            if(gls==poz[sol]) {
                g<<"YES\n";
                p=sol; val=gld-1;
                update(1,1,n);
            }else g<<"NO\n";
        }
    }
    return 0;
}