Cod sursa(job #546385)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 4 martie 2011 20:57:39
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <algorithm>
#include <map>
using namespace std;

#define N_MAX 100005
#define A_MAX 1<<18
#define fs first
#define sc second
#define md ((st+dr)>>1)
#define ST (nod<<1)
#define DR ((nod<<1)|1)

typedef pair <int,int> p;
typedef pair <p,int> pp;

pp ziduri[N_MAX];
map <int,int> nivele[N_MAX];

int aint[A_MAX];

int n,m,i,j,x,y,zidLovit;

void update(int nod,int st,int dr,int poz)
{
	if(st==dr)
	{
		aint[nod]=ziduri[poz].fs.sc;
		return ;
	}
	
	if(poz<=md)
		update(ST,st,md,poz);
	if(md<poz)
		update(DR,md+1,dr,poz);
	
	aint[nod]=max(aint[ST],aint[DR]);
}

int query(int nod,int st,int dr)
{
	int poz;
	
	if(x<ziduri[st].sc||aint[nod]<y)
		return 0;
	
	if(st==dr)
		return st;
	
	poz=query(DR,md+1,dr);
	if(!poz)
		poz=query(ST,st,md);
	
	return poz;
}

int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		
		ziduri[i].fs.fs=x;	ziduri[i].fs.sc=y;
		ziduri[i].sc=ziduri[i-1].sc+ziduri[i-1].fs.fs+1;
		
		update(1,1,n,i);
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		
		zidLovit=query(1,1,n);
		
		if(zidLovit)
		{
			if(++nivele[zidLovit][y]==ziduri[zidLovit].fs.fs)
			{
				printf("HIT %d %d YES\n",ziduri[zidLovit].sc,zidLovit);
					
				ziduri[zidLovit].fs.sc=y-1;
				update(1,1,n,zidLovit);
			}
			else
			{
				printf("HIT %d %d NO\n",ziduri[zidLovit].fs.fs-nivele[zidLovit][y]+ziduri[zidLovit].sc,zidLovit);
			}
		}
		else
			printf("MISS\n");
		
	}
	
	return 0;
}