Cod sursa(job #545270)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 2 martie 2011 23:31:32
Problema Walls Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <stdio.h>
#include <set>
#include <algorithm>
#define ll long long
#define NMAX 100005
#define LMAX (1<<18)
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,H[NMAX],p1,p2,in[NMAX];
struct pereche{ll a,b;};
pereche A[NMAX];
struct arbint{int a,b;};
arbint arb[LMAX];
ll px,py;
set <pii> C[NMAX];
void read()
{
	scanf("%d",&n);
	int i,x;
	ll poz=0;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&H[i]);
		A[i].a=poz; A[i].b=poz+x;
		poz+=x+1;
	}
}
int cb1()
{
	int i,step=(1<<17);
	for (i=0; step; step>>=1)
		if (i+step<=n && A[i+step].a<px)
			i+=step;
	return i;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void cstr(int st,int dr,int nod)
{
	if (st==dr)
	{
		in[st]=nod;
		arb[nod].a=H[st]; arb[nod].b=st;
		return ;
	}
	int mij=(st+dr)/2;
	cstr(st,mij,nod*2);
	cstr(mij+1,dr,nod*2+1);
	if (arb[2*nod].a>=arb[2*nod+1].a)
		arb[nod]=arb[2*nod];
	else
		arb[nod]=arb[2*nod+1];
}
void init()
{
	int i;
	cstr(1,n,1);
}
int find_poz(int st,int dr,int nod)
{
	if (st==dr)
		return st;
	int mij=(st+dr)/2;
	if (arb[2*nod+1].a>=p2 && arb[2*nod+1].b<=p1)
		return find_poz(mij+1,dr,nod*2+1);
	return find_poz(st,mij,nod*2);
}
void update(int poz)
{
	int i,nod=in[poz];
	arb[nod].a=H[poz]; arb[nod].b=poz;
	for (i=nod/2; i>0; i/=2)
		if (arb[2*i].a>=arb[2*i+1].a)
			arb[i]=arb[2*i];
		else
			arb[i]=arb[2*i+1];
}
void solve()
{
	int i,poz,val,caz;
	ll left;
	init();
	set <pii>:: iterator it;
	scanf("%d",&m);
	for (i=1; i<=m; i++)
	{
		scanf("%lld%lld",&px,&py);
		if (px<=A[1].a)
		{
			printf("MISS\n");
			continue ;
		}
		p1=cb1(); p2=py;
		poz=find_poz(1,n,1);
		if (H[poz]<p2)
		{
			printf("MISS\n");
			continue ;
		}
		caz=1;
		if (!C[poz].empty())
		{
			it=C[poz].upper_bound(mp(py,0));
			if ((*it).f!=py)
				caz=0;
			else
			{
				val=(*it).s+1;
				printf("HIT %lld %d ",A[poz].b-val+1,poz);
				C[poz].erase(it);
				if (val==A[poz].b-A[poz].a)
				{
					H[poz]=py-1;
					update(poz);
					printf("YES\n");
				}
				else
				{
					printf("NO\n");
					C[poz].insert(mp(py,val));
				}
			}
		}
		else
			caz=0;
		if (!caz)
		{
			C[poz].insert(mp(py,1));
			printf("HIT %lld %d ",A[poz].b,poz);
			if (A[poz].b-A[poz].a==1)
			{
				H[poz]=py-1;
				update(poz);
				printf("YES\n");
			}
			else
				printf("NO\n");
		}
	}
}
int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	read();
	solve();
	return 0;
}