Cod sursa(job #1685236)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 11 aprilie 2016 16:11:26
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#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!