Cod sursa(job #544532)

Utilizator freak93Adrian Budau freak93 Data 1 martie 2011 19:17:23
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

const char iname[] = "walls.in";
const char oname[] = "walls.out";
const int maxn = 100005;

map<pair<int, int>, int> M;
int arb[maxn * 4], h[maxn], w[maxn], n, m, i, step, poz, y;
long long X[maxn], x;

void build_arb(int nod, int left, int right) {
	if (left == right) {
		arb[nod] = h[left];
		return;
	}
	int mid = (left + right) >> 1;
	build_arb(nod * 2, left, mid);
	build_arb(nod * 2 + 1, mid + 1, right);
	arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

int find(int nod, int left, int right, int finish, int value) {
	if (left == right && arb[nod] >= value)
		return left;
	if (arb[nod] < value)
		return 0;
	int mid = (left + right) / 2;
	int rez = 0;
	if (mid < finish)
		rez = find(nod * 2 + 1, mid + 1, right, finish, value);
	if (rez > 0)
		return rez;
	return find(nod * 2, left, mid, finish, value);
}

void update(int nod, int left, int right, int poz, int value) {
	if (left == right) {
		arb[nod] = value;
		return;
	}
	int mid = (left + right) / 2;
	if (poz <= mid)
		update(nod * 2, left, mid, poz, value);
	else
		update(nod * 2 + 1, mid + 1, right, poz, value);
	arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

int main() {
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	scanf("%d", &n);
	for (i = 1; i <= n; ++i)
		scanf("%d%d", &w[i], &h[i]), X[i] = X[i - 1] + w[i - 1] + 1;
	build_arb(1, 1, n);
	scanf("%d", &m);
	while (m--) {
		scanf("%lld%d", &x, &y);
		for (step = 1; step < n; step <<= 1);
		for (i = 0; step; step >>= 1)
			if (i + step <= n && X[i + step] <= x)
				i += step;
		if (i == 0 || ((poz = find(1, 1, n, i, y)) == 0)) {
			printf("MISS\n");
			continue;
		}
		
		printf("HIT ");
		if (M.find(make_pair(poz, y)) == M.end())
			M[make_pair(poz, y)] = 0;
		int v;
		v = ++M[make_pair(poz, y)];
		printf("%lld %d ", X[poz] + w[poz] - v, poz);
		if(v == w[poz])
			h[poz] = y - 1, update(1, 1, n, poz, h[poz]), printf("YES\n");
		else
			printf("NO\n");
	}
}