Cod sursa(job #553610)

Utilizator ooctavTuchila Octavian ooctav Data 14 martie 2011 10:31:26
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"walls.in"};
const char OUT[] = {"walls.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 100005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N, M;
LL bz[NMAX], lg[NMAX];//le fac LL
int h[4*NMAX];
LL T;
int H;

void update(int st, int dr, int nod)
{
	if(st == dr)
	{
		h[nod] = H;
		return;
	}
	
	int mij = (st + dr) / 2;
	if(T <= mij)	update(st, mij, 2*nod);
	else			update(mij + 1, dr, 2*nod + 1);
	h[nod] = max(h[2*nod], h[2*nod + 1]);
}

int query(int st, int dr, int nod)
{
	if(h[nod] < H || bz[st] > T)	return -1;
	if(st == dr)	return st;
	
	int mij = (st + dr) / 2;
	int a = query(mij + 1, dr, 2*nod + 1);
	if(a == -1)	a = query(st, mij, 2*nod);
	return a;
}

void citi()
{
	scanf("%d", &N);
	int st = 1LL;
	FOR(i, 1, N)
	{
		LL x;
		int y;
		scanf("%lld%d", &x, &y);
		bz[i] = st;
		lg[i] = x;
		st += x + 1;
		T = i;H = y;
		update(1, N, 1);
	}
	scanf("%d", &M);
}

void rezolva()
{
	map<PII, int> Hit;//[NMAX];
	FOR(i, 1, M)
	{
		scanf("%lld%d", &T, &H);
		int ind = query(1, N, 1);
		if(ind == -1)
		{
			printf("MISS\n");
			continue;
		}
		int &nr = Hit[mp(ind, H)];
		nr++;
		printf("HIT %lld %d ", bz[ind] + lg[ind] - nr, ind);
		if(nr == lg[ind])
		{
			printf("YES\n");
			H--;
			T = ind;
			update(1, N, 1);
		}
		else	printf("NO\n");
	}
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	rezolva();
	return 0;
}