Pagini recente » Cod sursa (job #2582448) | Cod sursa (job #80868) | Cod sursa (job #2168154) | Cod sursa (job #2399263) | Cod sursa (job #1759804)
#include <fstream>
#include <queue>
#include <map>
#include <set>
using namespace std;
ifstream cin("walls.in");
ofstream cout("walls.out");
const int MAXN = 100000;
int width[1 + MAXN], height[1 + MAXN];
long long sum[1 + MAXN];
int tree[1 + 4 * MAXN];
void Update(int node, int left, int right, int index) {
if (left == right) {
tree[node] = left;
return;
}
int middle = (left + right) / 2;
if (index <= middle)
Update(2 * node, left, middle, index);
else
Update(2 * node + 1, middle + 1, right, index);
if (height[tree[2 * node + 1]] < height[tree[2 * node]])
tree[node] = tree[2 * node];
else
tree[node] = tree[2 * node + 1];
}
int BinarySearch(int value, int n) {
int left = 1, right = n, answer = 0;
while (left <= right) {
int middle = (left + right) / 2;
if (sum[middle] <= value) {
answer = middle;
left = middle + 1;
}
else
right = middle - 1;
}
return answer;
}
int Query(int node, int left, int right, int index, int target) {
if (left > index)
return -1;
if (right <= index) {
if (height[tree[node]] < target)
return -1;
if (left == right)
return tree[node];
}
int middle = (left + right) / 2;
int answer = Query(2 * node + 1, middle + 1, right, index, target);
if (answer != -1)
return answer;
return Query(2 * node, left, middle, index, target);
}
map<pair<int, int>, int> table;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> width[i] >> height[i];
sum[i] = sum[i - 1] + width[i] + 1;
Update(1, 1, n, i);
}
int tests;
cin >> tests;
for (int test = 1; test <= tests; test++) {
int x, y;
cin >> x >> y;
int answer = Query(1, 1, n, BinarySearch(x + 1, n), y);
if (answer == -1) {
cout << "MISS\n";
continue;
}
cout << "HIT ";
table[make_pair(answer, y)]++;
int where = table[make_pair(answer, y)];
cout << sum[answer] - where << " " << answer << " ";
if (where == width[answer]) {
height[answer] = y - 1;
Update(1, 1, n, where);
cout << "YES\n";
}
else
cout << "NO\n";
}
return 0;
}