Cod sursa(job #545044)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 2 martie 2011 17:15:08
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <map>
using namespace std;
#define nmax 100010

struct punct
{
	int x, y, w;
} v[nmax];

int n, poz, val, arb[4*nmax], m, p[nmax], nod, rn;
char d[4*nmax], f[4*nmax];
map <int, int> g[nmax];

void update(int nod, int l, int r)
{
	if (l==1) f[nod]=1;
	if (l==r) 
	{
		arb[nod]=poz;
		d[nod]=1;
		p[poz]=nod;
	} else
	{
		int m=(l+r)/2;
		if (poz<=m) update(2*nod, l, m); else
			update(2*nod+1, m+1, r);
		if (v[arb[2*nod+1]].y>=v[arb[2*nod]].y) 
			arb[nod]=arb[2*nod+1]; else
				arb[nod]=arb[2*nod];
	}
}

int search(int a, int b)
{
	int m, r=0;
	while (a<=b)
	{
		m=(a+b)/2;
		if (v[m].x<val) 
		{
			r=m;
			a=m+1;
		} else b=m-1;
	}
	return r;
}

void up(int nod)
{
	if (v[arb[rn]].y>=val || nod==1); else
	{
		if (nod%2) 
			if (v[arb[nod-1]].y>=v[arb[rn]].y) rn=nod-1;
		up(nod/2);
	}
}

int query(int nod)
{
	if (d[nod]) return arb[nod];
	if (arb[2*nod+1]==arb[nod] || v[arb[2*nod+1]].y>=val) 
		return query(2*nod+1); else
			return query(2*nod);
}

int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	int i, w, h, x, y;
	scanf("%d",&n);
	v[0].x=-1;
	for (i=1; i<=n; i++)
	{
		scanf("%d %d", &w, &h);
		v[i].y=h;
		v[i].x=v[i-1].x+1+w;
		v[i].w=w;
		poz=i;
		val=h;
		update(1, 1, n);
	}
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d %d",&x, &y);
		val=x;
		x=search(1, n);
		val=y;
		rn=p[x];
		if (x) up(p[x]);
		nod=rn;
		if (v[arb[nod]].y<y || !x) printf("MISS\n"); else
		{
			printf("HIT ");
			poz=query(nod);
			printf("%d ",v[poz].x-g[poz][y]);
			printf("%d ",poz);
			g[poz][y]++;
			if (g[poz][y]==v[poz].w)
			{
				printf("YES\n");
				v[poz].y=y-1;
				val=v[poz].y;
				update(1, 1, n);
			} else printf("NO\n");
		}
	}
}