Cod sursa(job #549119)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 8 martie 2011 10:10:06
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <algorithm>
#include <map>

using namespace std;

#define MAXN 100010

long long st;
long long XWall[MAXN];
int HWall[4*MAXN], Lat[MAXN];
int i,ind,N,M,Y,y, x, X;

int find1(int nod, int st, int dr, int X, int H)
{
	if (st>dr || XWall[st]>X || HWall[nod]<H) return -1;
	if (st==dr) return st;
	int mij = (st+dr)>>1;
	int aux = find1((nod<<1)+1, mij+1, dr, X,H);
	if (aux == -1)
		aux = find1((nod<<1), st, mij, X,H);
	return aux;
}

void update(int nod, int st, int dr, int poz, int X)
{
	if (st>dr) return;
	if (st==dr){
		HWall[nod] = X;
		return;
	}
	int mij=(st+dr)>>1;
	if (mij >= poz)
		update((nod<<1), st, mij, poz, X);
	else
		update((nod<<1)+1, mij+1, dr, poz, X);
	HWall[nod] = max(HWall[(nod<<1)], HWall[(nod<<1)+1]);
}

int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	
	scanf("%d",&N);
	st = 1LL;
	for (i=1; i<=N; ++i){
		scanf("%d %d",&x,&y);
		XWall[i] = st;
		st += x+1;
		Lat[i] = x;
		update(1, 1, N, i, y);
	}
	
	map<pair<int, int>, int> Hit;
	scanf("%d",&M);
	for (i=1; i<=M; ++i){
		scanf("%d %d",&X,&Y);
		ind = find1(1, 1, N, X, Y);
		if (ind == -1){
			printf("MISS\n");
			continue;
		}
		int &nr = Hit[make_pair(ind, Y)];
		++nr;
		printf("HIT %lld ", XWall[ind]+Lat[ind]-nr);
		printf("%d ", ind);
		if (nr == Lat[ind]){
			printf("YES\n");
			update(1, 1, N, ind, Y-1);
		}
		else 
			printf("NO\n");
	}
	
	return 0;
}