Pagini recente » Cod sursa (job #812578) | Cod sursa (job #2752082) | Cod sursa (job #1798774) | Cod sursa (job #1706156) | Cod sursa (job #1685236)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
ifstream fin("walls.in");
ofstream fout("walls.out");
const int dim = 100005;
int n;
long long partX[dim];
int aint[dim * 4], width[dim], height[dim];
map< pair<int, int>, int > myMap;
int binarySearch(int val) {
int left = 1, right = n, ret = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (partX[mid] <= val) {
left = mid + 1;
ret = mid;
}
else
right = mid - 1;
}
return ret;
}
void update(int cur, int l, int r, int pos) {
if (l == r) {
aint[cur] = l;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(2 * cur, l, mid, pos);
else
update(2 * cur + 1, mid + 1, r, pos);
if (height[aint[2 * cur]] > height[aint[2 * cur + 1]])
aint[cur] = aint[2 * cur];
else
aint[cur] = aint[2 * cur + 1];
}
int query(int cur, int l, int r, int pos, int hitY) {
if (l > pos)
return -1;
if (r <= pos) {
if (height[aint[cur]] < hitY)
return -1;
if (l == r)
return aint[cur];
}
int mid = (l + r) / 2;
int ret = query(2 * cur + 1, mid + 1, r, pos, hitY);
if (ret == -1)
ret = query(2 * cur, l, mid, pos, hitY);
return ret;
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> width[i] >> height[i];
partX[i] = partX[i - 1] + 1 + width[i];
update(1, 1, n, i);
}
int queryCount;
fin >> queryCount;
while (queryCount--) {
int x, y;
fin >> x >> y;
int ans = query(1, 1, n, binarySearch(x + 1), y);
if (ans == -1) {
fout << "MISS\n";
continue;
}
fout << "HIT ";
int aux = ++myMap[make_pair(ans, y)];
fout << partX[ans] - aux << ' ' << ans << ' ';
if (aux == width[ans]) {
height[ans] = y - 1;
update(1, 1, n, ans);
fout << "YES\n";
}
else
fout << "NO\n";
}
return 0;
}
//Trust me, I'm the Doctor!