Cod sursa(job #543845)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 28 februarie 2011 17:39:14
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>

#include <map>

using namespace std;

struct vect
{
	int x, y;
};

int n, m;
vect v[100005];
int aint[262150];
long long poz[100005];

map <pair <int, int>, int> h;

void update (int nod, int st, int dr, int poz, int x)
{
	if (st == dr)
	{
		aint[nod] = x;
		return;
	}
	
	int m = (st + dr) >> 1;
	
	if (poz <= m)
		update (nod * 2, st, m, poz, x);
	else
		update (nod * 2 + 1, m + 1, dr, poz, x);
	
	aint[nod] = max (aint[nod * 2], aint[nod * 2 + 1]);
}

int query (int nod, int st, int dr, int x, int y)
{
	if (x < poz[st] || y > aint[nod])
		return 0;
	if (st == dr)
		return st;
	
	int sol, m = (st + dr) >> 1;
	
	sol = query (nod * 2 + 1, m + 1, dr, x, y);
	if (!sol)
		sol = query (nod * 2, st, m, x, y);
	return sol;
}

int main ()
{
	freopen ("walls.in", "r", stdin);
	freopen ("walls.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, x, y, sol;
	
	for (i = 1; i <= n; i ++)
	{
		scanf ("%d %d", &v[i].x, &v[i].y);
		
		update (1, 1, n, i, v[i].y);
		poz[i] = poz[i - 1] + 1 + v[i - 1].x;
	}
	
	scanf ("%d", &m);
	
	for (i = 1; i <= m; i ++)
	{
		scanf ("%d %d", &x, &y);
		
		sol = query (1, 1, n, x, y);
		if (!sol)
		{
			printf ("MISS\n");
			continue;
		}
		printf ("HIT ");
		
		if (h.find (make_pair (sol, y)) != h.end ())
			h[make_pair (sol, y)] ++;
		else
			h[make_pair (sol, y)] = 1;
		x = poz[sol] + v[sol].x - h[make_pair (sol, y)];
		
		printf ("%d %d ", x, sol);
		if (x == poz[sol])
		{
			printf ("YES\n");
			update (1, 1, n, sol, y - 1);
		}
		else
			printf ("NO\n");
	}
	return 0;
}