Cod sursa(job #543690)

Utilizator katakunaCazacu Alexandru katakuna Data 28 februarie 2011 14:59:37
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;

#define Nmax 100010

struct wall {long long st, dr;} v[Nmax];

int n, m, lst, x, y, poz, val;
int AI[4 * Nmax], H[Nmax];
map < pair <int, int>, int > M;

void citire () {

	int i, w;

	scanf ("%d", &n); v[0].dr = -1;
	for (i = 1; i <= n; i++) {
		scanf ("%d %d", &w, &H[i]);
		v[i].st = v[i-1].dr + 2;
		v[i].dr = v[i].st + w - 1;
	}
}

#define MIJ ((st + dr) >> 1)
#define N1 (nod << 1)
#define N2 ((nod << 1) + 1)

void make_arb (int nod, int st, int dr) {

	if (st == dr) {
		AI[nod] = H[st];
		return ;
	}

	make_arb (N1, st, MIJ);
	make_arb (N2, MIJ + 1, dr);

	AI[nod] = max (AI[N1], AI[N2]);
}

void update_arb (int nod, int st, int dr) {

	if (st == dr) {
		AI[nod] = val;
		return ;
	}

	if (poz <= MIJ) update_arb (N1, st, MIJ);
	else update_arb (N2, MIJ + 1, dr);

	AI[nod] = max (AI[N1], AI[N2]);
}

int query_arb (int nod, int st, int dr) {

	if (st > lst || AI[nod] < y) return 0;
	if (st == dr) return st;

	int bla = query_arb (N2, MIJ + 1, dr);
	if (!bla) bla = query_arb (N1, st, MIJ);

	return bla;
}

void rezolva () {

	int p, u, mij, w;

	make_arb (1, 1, n);

	scanf ("%d", &m);
	for (; m; m--) {
		scanf ("%d %d", &x, &y);
		p = 1; u = n; lst = 0;
		while (p <= u) {
			mij = (p + u) >> 1;
			if (v[mij].st < x) {
				lst = mij;
				p = mij + 1;
			}
			else
				u = mij - 1;
		}

		w = query_arb (1, 1, n);

		if (!w) {
			printf ("MISS\n");
			continue;
		}

		printf ("HIT ");

		if (M.find (make_pair(w,y)) == M.end ()) {
			printf ("%lld ", v[w].dr);
			printf ("%d ", w);
			M[make_pair(w,y)] = 1;
		}
		else {
			printf ("%lld ", v[w].dr - (long long)M[make_pair(w,y)]);
			printf ("%d ", w);
			M[make_pair(w,y)]++;
		}

		if (v[w].dr - (long long)M[make_pair(w,y)] < v[w].st) {
			printf ("YES\n");
			poz = w; val = y-1;
			update_arb (1, 1, n);
		}
		else
			printf ("NO\n");
	}
}

int main () {

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

	citire ();
	rezolva ();

	return 0;
}