Cod sursa(job #543946)

Utilizator savimSerban Andrei Stan savim Data 28 februarie 2011 19:58:27
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <stdio.h>
#include <set>
#include <algorithm>

using namespace std;

#define MAX_N 100010
#define MAX_P 131072
#define inf 2147000000

int n, m, p2, x, y;
int vine[MAX_P * 2 + 10];

typedef set <pair <int, int> > MYSET;
MYSET s[MAX_N];

struct wall {
	int w, h, start;
} A[MAX_N];

void build_tree() {
	p2 = 1;
	while (p2 < n)
		p2 *= 2;

	for (int i = p2; i <= p2 + n - 1; i++) 
    	vine[i] = i - p2 + 1;

	for (int i = p2 - 1; i > 0; i--) 
		if (A[vine[i * 2]].h > A[vine[i * 2 + 1]].h) 
			vine[i] = vine[i * 2];
		else 
			vine[i] = vine[i * 2 + 1];
}

inline int get_left() {
	int st = 0, dr = n + 1, mid = 0, ret = 0;
	while (st + 1 < dr) {
    	mid = (st + dr) / 2;

		if (A[mid].start > x)
			dr = mid;
		else {
			st = mid;
			ret = max(ret, mid);
		}
	}

	return ret;
}

inline int query(int nod, int st, int dr, int left, int right) {
	if (st > right || dr < left)
		return 0;

	if (A[vine[nod]].h < y)
		return 0;

	if (nod >= p2)
		return vine[nod];

	int mid = (st + dr) >> 1;
	int v = query(nod * 2 + 1, mid + 1, dr, left, right);
	if (A[v].h >= y)
		return v;
	return query(nod * 2, st, mid, left, right);
}

void update(int x) {
	while (x) {
		if (A[vine[x * 2]].h > A[vine[x * 2 + 1]].h) 
			vine[x] = vine[x * 2];
		else 
			vine[x] = vine[x * 2 + 1];

		x = x >> 1;
	}
}

void insert_set(int pos, int y) {
   	MYSET::iterator it = s[pos].upper_bound(make_pair(y, 0));
   	int val = it->second;

   	if (it -> first == y) {
   		s[pos].erase(it);
   		s[pos].insert(make_pair(y, val + 1));
   	}
   	else
   		s[pos].insert(make_pair(y, 1));

	it = s[pos].upper_bound(make_pair(y, 0));
	val = it->second;

	printf("HIT %d %d ", A[pos].start + A[pos].w - val, pos);
	if (val < A[pos].w) 
		printf("NO\n");
	else {
    	printf("YES\n");

		A[pos].h = y - 1;
		update((p2 + pos - 1) >> 1);
	}
}

void solve(int pos) {
	int pmax = query(1, 1, p2, 1, pos); //cel mai din dreapta dreptunghi mai inalt decat y

	if (y > A[pmax].h)
		printf("MISS\n");
	else 
		insert_set(pmax, y);
}

int main() {

	freopen("walls.in", "r", stdin);
    freopen("walls.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &A[i].w, &A[i].h);

		if (i == 1)
			A[i].start = 1;
		else
			A[i].start = min(1LL * A[i - 1].start + A[i - 1].w + 1, 1LL * inf);
	}

	build_tree();

	for (int i = 1; i <= n; i++)
		s[i].insert(make_pair(inf, 0));

	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
    	scanf("%d %d", &x, &y); //lovitura de tun este la coordonata x, y

		int pos = get_left(); //gasesc pozitia primului dreptunghi din stanga coordonatei x,y

		if (pos == 0)
			printf("MISS\n");
		else
			solve(pos);
	}

	return 0;
}