Cod sursa(job #545020)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 2 martie 2011 16:49:01
Problema Walls Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <algorithm>
#include <map>

using namespace std;

#define MAXN 100010

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

int find1(int nod, int st, int dr, long long 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 = 1;
	for (i=1; i<=N; ++i){
		scanf("%lld %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("%lld %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 == y){
			printf("YES\n");
			update(1, 1, N, ind, y-1);
		}
		else 
			printf("NO\n");
	}
	
	return 0;
}