Cod sursa(job #556228)

Utilizator CezarMocanCezar Mocan CezarMocan Data 16 martie 2011 00:06:49
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <cstdio>
#include <map>
#include <algorithm>


using namespace std;

const int maxN = 100100;

struct rectangle {
	int x1, x2, y;
};

int N, M;
rectangle V[maxN];
int st[4 * maxN];
int goodNod, goodLeft, goodRight;
int poz;
map <int, int> broken[maxN];

inline void build_st(int nod, int left, int right) {
	int m = (left + right) / 2;

	if (left == right) {
		st[nod] = left;
		return;
	}

	build_st(2 * nod, left, m);
	build_st(2 * nod + 1, m + 1, right);

	if (V[st[2 * nod]].y > V[st[2 * nod + 1]].y)
		st[nod] = st[2 * nod];
	else
		st[nod] = st[2 * nod + 1];
}

inline void query1(int nod, int left, int right, int x, int y, int limVal) {
	int m = (left + right) / 2;

	if (x <= left && right <= y) {
		if (V[st[nod]].y >= limVal) {
			if (right > goodRight) {
				goodLeft = left;
				goodRight = right;
				goodNod = nod;
			}
		}

		return;
	}

	if (x <= m)
		query1(2 * nod, left, m, x, y, limVal);
	if (y > m)
		query1(2 * nod + 1, m + 1, right, x, y, limVal);
}

void query2(int nod, int left, int right, int limVal) {
	int m = (left + right) / 2;
	if (left == right) {
		poz = left;
		return;
	}

	if (V[st[2 * nod + 1]].y >= limVal) {
		query2(2 * nod + 1, m + 1, right, limVal);
		return;
	}

	query2(2 * nod, left, m, limVal);
}

inline void update(int nod, int left, int right, int poz) {
	int m = (left + right) / 2;

	if (left == right) 
		return;
	
	if (poz <= m)
		update(2 * nod, left, m, poz);
	else
		update(2 * nod + 1, m + 1, right, poz);


	if (V[st[2 * nod]].y > V[st[2 * nod + 1]].y)
		st[nod] = st[2 * nod];
	else
		st[nod] = st[2 * nod + 1];
}

inline int bsearch(int x) {
	int left = 1, right = N;
	int m;

	if (x <= V[1].x2)
		return 0;
	if (x > V[N].x2)
		return N;

	while (left <= right) {
		m = (left + right) / 2;
		if (V[m].x2 < x && V[m + 1].x2 >= x) 
			return m;
		
		if (V[m].x2 < x)
			left = m + 1;
		else
			right = m - 1;
	}

	return right;
}

int main() {
	int i, j, a, b;
	freopen("walls.in", "r", stdin);
	freopen("walls.out", "w", stdout);

	scanf("%d", &N);

	V[0].x2 = -1;
	for (i = 1; i <= N; i++) {
		scanf("%d%d", &a, &b);
		V[i].x1 = V[i - 1].x2 + 2;
		V[i].x2 = V[i].x1 + a - 1;
		V[i].y = b;

	}

	build_st(1, 1, N);

	scanf("%d", &M);

	for (i = 1; i <= M; i++) {
		scanf("%d%d", &a, &b);

		goodLeft = goodRight = goodNod = 0;

		int pozSir = bsearch(a);

//		fprintf(stderr, "a = %d, pozSir = %d\n", a, pozSir);

		if (pozSir == 0) {
			printf("MISS\n");
			continue;
		}

		query1(1, 1, N, 1, pozSir, b);

		if (goodNod == 0) {
			printf("MISS\n");
			continue;
		}

//		fprintf(stderr, "%d  -> %d %d\n", i, goodLeft, goodRight);
		poz = 0;
		query2(goodNod, goodLeft, goodRight, b);

		//il am pe poz si umblu la map-ul cu grosimea chestiilor sparte
		
		bool ok = 0;

		broken[poz][b]++;
		int br = broken[poz][b];
		if (br == (V[poz].x2 - V[poz].x1 + 1)) {
			ok = 1;
			V[poz].y = b - 1;
			update(1, 1, N, poz);
		}

		printf("HIT %d %d ", V[poz].x2 - br + 1, poz);
		if (ok)
			printf("YES\n");
		else
			printf("NO\n");

	}


	return 0;
}