Cod sursa(job #729807)

Utilizator BoSs_De_BosSSeFu SeFiLoR BoSs_De_BosS Data 30 martie 2012 10:38:09
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<iostream>
#include<fstream>
#include<map>
using namespace std;

ifstream in("walls.in");
ofstream out("walls.out");

const int N = 100010;

int n,m,aint[3*N],h[N],w[N],xx,y,poz,x[N];
map<pair<int,int>, int> ha;
map<pair<int,int>, int>::iterator it;

void update(int nod, int pozx, int pozy) {
	if(pozx == pozy) {
		aint [nod] = pozx;
		return;
	}
	
	int mi = (pozx + pozy)>>1;
	
	if(poz<=mi)
		update(2*nod, pozx, mi);
	else
		update(2*nod+1, mi+1, pozy);
	
	aint[nod] = h[aint[2*nod]] > h[aint[2*nod+1]] ? aint[2*nod] : aint[2*nod+1];
}

int q(int nod, int pozx, int pozy) {
	if(pozx > poz)
		return -1;
	
	if(pozy <= poz) {
		
		if(pozx == pozy && h[aint[nod]]>=y)
			return aint[nod];
		
		if(h[aint[nod]]<y || pozx == pozy)
			return -1;
	}
	
	int mi = (pozx + pozy)>>1;
	
	int r = q(2*nod+1, mi+1, pozy);
	
	if(r == -1)
		r = q(2*nod, pozx, mi);
	
	return r;
}

int main() {
	int i,pas;
	
	in >> n;
	
	x[0] = -1;
	
	for(i=1;i<=n;++i) {
		in >> w[i] >> h[i];
		
		x[i] = x[i-1]+w[i] + 1;
		poz = i;
		update(1,1,n);
	}
	
	in >> m;
	
	while(m--) {
		
		in >> xx >> y;
		
		pas = 1<<18;
		for(i = 0; pas!=0; pas>>=1)
			if(i+pas<=n && x[i+pas]<xx)
				i+=pas;
		
		poz = i;
		
		int res = q(1,1,n),ver = 0;
		
		if(res == -1) {
			out << "MISS\n";
			continue;
		}
		
		out << "HIT ";
		
		++ha[make_pair(res, y)];
		it = ha.find(make_pair(res,y));
		
		out << x[res] - it->second+1 << " ";
		
		if(it->second == w[res]) {
			ver = 1;
			
			h[res] = y - 1;
			poz = res;
			update(1,1,n);
		}
		
		out << res << " ";
		
		if(ver)
			out << "YES\n";
		else
			out << "NO\n";
	}
	
	return 0;
}