Cod sursa(job #545279)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 2 martie 2011 23:53:04
Problema Walls Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 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],a,b;
struct pereche{ll a,b;};
pereche A[NMAX];
int 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]=H[st]; 
		return ;
	}
	int mij=(st+dr)/2;
	cstr(st,mij,nod*2);
	cstr(mij+1,dr,nod*2+1);
	arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
void init()
{
	int i;
	cstr(1,n,1);
}
int query(int st,int dr,int nod)
{
	if (a<=st && dr<=b)
		return arb[nod];
	if (a>dr || b<st)
		return 0;
	int mij=(st+dr)/2;
	return max(query(st,mij,nod*2),query(mij+1,dr,nod*2+1));
}
void update(int poz)
{
	int i,nod=in[poz];
	arb[nod]=H[poz]; 
	for (i=nod/2; i>0; i/=2)
		arb[i]=max(arb[2*i],arb[2*i+1]);
}
int find_poz()
{
	int i,step=(1<<17);
	for (i=0; step; step>>=1)
	{
		a=i+step; b=p1;
		if (i+step<=p1 && query(1,n,1)>=p2)
			i+=step;
	}
	return i;
}
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();
		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;
}