// http://infoarena.ro/problema/walls
#include <fstream>
#include <map>
using namespace std;
#define maxSize 100001
#define xx first
#define yy second
#define leftSon (node<<1)
#define rightSon (node<<1)+1
ifstream in("walls.in");
ofstream out("walls.out");
struct stuff {
long long x;
int width;
};
int nrWalls,bombs;
stuff wall[maxSize];
int tree[4*maxSize];
// de cate ori s-a lovit zidul first la inaltimea second
map< pair<int,int>, int> hits;
void update(int node,int left,int right,int position,int height);
int query(int node,int left,int right,int x,int height);
int main() {
in >> nrWalls;
int currentHeight;
for(int i=1;i<=nrWalls;i++) {
// latimea si inaltimea zidului
in >> wall[i].width >> currentHeight;
// abscisa sa este abscisa zidului precedent
// plus latimea acestuia plus unu (distanta intre ziduri)
wall[i].x = wall[i-1].x + wall[i-1].width + 1;
// se introduce inaltimea sa in arborele de intervale
update(1,1,nrWalls,i,currentHeight);
}
in >> bombs;
int targetWall,hitBlock;
pair<int,int> currentBomb;
for(int i=1;i<=bombs;i++) {
in >> currentBomb.xx >> currentBomb.yy;
targetWall = query(1,1,nrWalls,currentBomb.xx,currentBomb.yy);
if(!targetWall)
out << "MISS\n";
else {
out << "HIT ";
// creste numarul loviturilor in zid la inaltimea ordonatei bombei
hits[make_pair(targetWall,currentBomb.yy)]++;
// abscisa celului lovite (abscisa zidului plus latimea acestuia
// minus de cate ori a fost bombardata linia resprectiva
hitBlock = (int) wall[targetWall].x + wall[targetWall].width - hits[make_pair(targetWall,currentBomb.yy)];
out << hitBlock << " " << targetWall << " ";
// daca abscisa celulei lovite este egala
// cu abscisa zidului (s-a distrus un nivel intreg)
if(hitBlock == wall[targetWall].x) {
out << "YES\n";
// se actualizeaza inaltimea zidului curent cu ordonata bombei minus unu
update(1,1,nrWalls,targetWall,currentBomb.yy-1);
}
else
out << "NO\n";
}
}
in.close();
out.close();
return (0);
}
void update(int node,int left,int right,int position,int height) {
if(left == right)
tree[node] = height;
else {
int middle = (left + right) >> 1;
if(position <= middle)
update(leftSon,left,middle,position,height);
else
update(rightSon,middle+1,right,position,height);
tree[node] = max(tree[leftSon],tree[rightSon]);
}
}
int query(int node,int left,int right,int x,int height) {
// daca ne aflam cu intervalul in dreapta
// zidului cautat iar subarborele ofera un
// zid de inaltime mai mare decat
// inaltimea (ordonata) bombei
if(wall[left].x <= x && height <= tree[node])
if(left == right)
return left;
else {
int middle = (left + right) >> 1;
// prima data se cauta in subarborele drept
// (pentru a fi la dreapta zidului cautat)
int answer = query(rightSon,middle+1,right,x,height);
// daca nu s-a gasit un zid care sa
// corespunda pozitiei si ordonatei bombei
if(!answer)
// se cauta in subarborele stang
// (zidul sigur se afla aici datorita
// modului in care am efectuat cautarea)
return query(leftSon,left,middle,x,height);
else
return answer;
}
else
return (0);
}