Cod sursa(job #545687)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 3 martie 2011 20:17:33
Problema Walls Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
#define N_MAX 100010
#define mp make_pair
struct block{
	long long x1, x2;
	int	h;
};
block v[N_MAX];
set < pair<int, int> > H[N_MAX];
set < pair<int, int> >::iterator it;
int t[3*N_MAX];
int n, m;
int a, b, poz, val;
long long h;
void build(int p, int q, int i) {
	if(p == q) {
		t[i] = v[p].h;
		return;
	}
	int m = (p+q)/2;
	build(p, m, 2*i);
	build(m+1, q, 2*i+1);
	t[i] = max(t[2*i], t[2*i+1]);
}
void update(int p, int q, int i) {
	if(p == q) {
		t[i] = val;
		return;
	}
	int m = (p+q)/2;
	if(a <= m) update(p, m, 2*i);
	else update(m+1, q, 2*i+1);
	t[i] = max(t[2*i], t[2*i+1]);
}
inline int find_pos(long long x) {
	int step = 0, pos = 0;
	for(; (1<<step) <= n; ++step); step--;
	for(int i = step; i >= 0; --i)
		if(pos + (1<<i) <= n && v[pos+(1<<i)].x1 < x) pos += (1<<i);
	return pos;
}
void query(int p, int q, int i) {
	if(poz) return;
	if(t[i] < h) return;
	if(p == q){
		poz = p;
		return ;
	}
	int m = (p+q)/2;
	if(b > m) query(m+1, q, 2*i+1);
	if(a <= m) query(p, m, 2*i);
}
void destroyed(int x){
	printf("HIT %lld ", v[x].x1);
	printf("%d ",x);
	printf("YES\n");
	a = x;
	val = h-1;
	update(1, n, 1);
}
void ciuruit(int x) {
	it = H[x].upper_bound(mp(h, 0));
	int  rase = 0;
	if(it == H[x].end() || it->first > h)
		rase = 0;
	else rase = it->second;
	if(v[x].x2 - v[x].x1 == rase) destroyed(x);
	else {
		printf("HIT %lld ", v[x].x2-rase);
		printf("%d ", x);
		printf("NO\n");
		if(it != H[x].end()) H[x].erase(it);
		H[x].insert(mp(h, rase+1));
	}
}
void solve(long long x, long long y) {
	b = find_pos(x);
	a = 1;
	poz = 0; 
	h = y;
	query(1, n, 1);
	if(poz == 0){
		printf("MISS\n");
		return ;
	}
	ciuruit(poz);
}
int main() {
	freopen("walls.in", "r", stdin);
	freopen("walls.out", "w", stdout);
	scanf("%d", &n);
	
	for(int i = 1;  i <= n; ++i) {
		int w, h;
		scanf("%d%d", &w, &h);
		v[i].h = h;
		if(i != 1)
			v[i].x1 = v[i-1].x2 + 2;
		else 
			v[i].x1 = 1;
		v[i].x2 = v[i].x1 + w - 1;
	}
	build(1, n, 1);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i) {
		long long x, y;
		scanf("%lld%lld", &x, &y);
		solve(x, y);
	}
	return 0;
}