Cod sursa(job #544248)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 1 martie 2011 12:00:17
Problema Walls Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#define MAXN 100010
using namespace std;
map<pair<int,int>,int> MP;
int N,M;
struct wall{

	int width, height;
	long long xfin;
} V[MAXN];

int Ai[MAXN*4];

inline int FMX(int a,int b){
	return (a>b?a:b);
}

void place_maxim(int nod,int st,int dr,int poz,int repl){

	if (st==dr){ 
		Ai[nod]=repl;
		return ;
	}

	int m=(st+dr)/2;
	if (poz<=m) place_maxim(nod*2,st,m,poz,repl); else
		place_maxim(nod*2+1,m+1,dr,poz,repl);

	Ai[nod]=FMX(Ai[nod*2],Ai[nod*2+1]);
}

int get_maxim(int nod,int st,int dr,int A,int B){

	if (A<=st && dr<=B) return Ai[nod];

	int m=(st+dr)/2;

	int partmax=0;

	if (A<=m) partmax=FMX(partmax,get_maxim(nod*2,st,m,A,B));
	if (B>m) partmax=FMX(partmax,get_maxim(nod*2+1,m+1,dr,A,B));

	return partmax;
}

void build_Ai(int nod,int st,int dr){
	if (st==dr){
		Ai[nod]=V[st].height;
		return ;
	}

	int m=(st+dr)/2;

	build_Ai(nod*2,st,m);
	build_Ai(nod*2+1,m+1,dr);

	Ai[nod]=FMX(Ai[nod*2],Ai[nod*2+1]);
}

int cbin_which_wall(long long xcd){
	int REZ=0;
	int st=1,dr=N;

	while (st<=dr){
		int m=(st+dr)/2;
		if (V[m].xfin < xcd){ 
			REZ=m;
			st=m+1;
		} else dr=m-1;
	}

	return REZ;
}

int cbin_which_hit(long long ycd,int wstart){

	int REZ=0;
	int st=1;
	int dr=wstart;

	while (st<=dr){
		int m=(st+dr)/2;

		long long hmax=get_maxim(1,1,N,m,wstart);
		if (hmax>=ycd){
			REZ=m;
			st=m+1;
		} else dr=m-1;
	}

	return REZ;
}
		

int main(){

	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);

	scanf("%d",&N);

	for (int i=1;i<=N;++i){
		scanf("%d%d",&V[i].width,&V[i].height);
		if (i==1) V[i].xfin=V[i].width; else V[i].xfin=V[i-1].xfin+1+V[i].width;
	}

	build_Ai(1,1,N);

	scanf("%d",&M);

	for (int i=1;i<=M;++i){

		long long CX,CY;

		scanf("%lld %lld",&CX,&CY);

		int wallstart=cbin_which_wall(CX);
		int hitwall=cbin_which_hit(CY,wallstart);

		if (hitwall==0) {
			printf("MISS\n");
			continue ;
		}

		int nafectate=(++MP[make_pair(hitwall,(int)CY)]);
		long long chit=V[hitwall].xfin-nafectate+1;

		printf("HIT %lld %d ",chit,hitwall);

		if (nafectate==V[hitwall].width){
			printf("YES\n");
			place_maxim(1,1,N,hitwall,(int)CY-1);
		} else printf("NO\n");
	}




	fclose(stdin);
	fclose(stdout);

	return 0;
}