Cod sursa(job #545177)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 2 martie 2011 20:47:41
Problema Walls Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <stdio.h>
#include <algorithm>
#define ll long long
#define NMAX 100005
#define LMAX (1<<18)
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,aib[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];
}
int lsb(int x)
{
	return x & -x;
}
void upd1(int poz,int val)
{
	int i;
	for (i=poz; i<=n; i+=lsb(i))
		aib[i]+=val;
}
ll suma(int poz)
{
	int i;
	ll s=0;
	for (i=poz; i>0; i-=lsb(i))
		s+=aib[i];
	return s;
}
void init()
{
	int i;
	cstr(1,n,1);
	for (i=1; i<=n; i++)
		upd1(i,A[i].b-A[i].a);
}
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;
	ll left;
	init();
	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 ;
		}
		left=suma(poz)-suma(poz-1);
		if (left>1)
			printf("HIT %lld %d NO\n",A[poz].a+left,poz);
		else
			printf("HIT %lld %d YES\n",A[poz].a+left,poz);
		upd1(poz,-1); left--;
		if (left==0)
		{
			upd1(p1,A[poz].b-A[poz].a);
			H[poz]=py-1;
			update(poz);
		}
	}
}
int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	read();
	solve();
	return 0;
}