Cod sursa(job #541866)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 25 februarie 2011 14:56:15
Problema Walls Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 1.44 kb
#include<cstdio>
#include<algorithm>
#include<vector>


using namespace std;
#define sh short int
#define LL long long
#define pb push_back

#define NM 100005
int x,y,px;
vector<LL>x1;
vector<int>y1,zid;
int N,M;
LL nr;
inline void citire()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	scanf("%d",&N);
	int i;
	LL sx=0,ss=0;
	for (i=1; i<=N; ++i)
	{
		scanf("%d%d",&x,&y);
		ss=sx+x;
		for (LL j=sx+1; j<=ss; ++j)
		{
			++sx;
			x1.pb(sx);
			y1.pb(y);
			zid.pb(i);
		//	printf("%lld %d\n",sx,y);
		}
		nr+=x;
		++sx;
	}
	--nr;
}
inline void exista (int px)
{
	while (px>=0 && y1[px]<y)
		--px;
	if (px==-1)
	{
		if (y1[0]<y)
			printf("MISS\n");
		else
		{
			printf("HIT 1 %d YES\n",zid[0]);
			y1[0]=y-1;
		}
		return;
	}
	if (px==0)
	{
		if (y1[px]>=y)
		{
			printf("HIT %lld %d YES\n",x1[px],zid[px]);
		y1[px]=y-1;
		return;
		}
		printf("HIT %lld %d NO\n",x1[px],zid[px]);
		y1[px]=y-1;
		return;
	}
	if (x1[px-1]+1==x1[px])
	{
		printf("HIT %lld %d NO\n",x1[px],zid[px]);
		y1[px]=y-1;
		return;
	}
	printf("HIT %lld %d YES\n",x1[px],zid[px]);
	y1[px]=y-1;
}
inline void citesc2()
{
	scanf("%d",&M);
	vector<LL>::iterator g;
	while (M--)
	{
		scanf("%d%d",&x,&y);
		g=lower_bound(x1.begin(),x1.end(),x);
		if (*g<0)
		{
			--g;
		}
		while (*g>x)
			--g;
		px=g-x1.begin();
		exista(px);
	}
}
int main()
{
	citire();
	citesc2();
	return 0;
}