Cod sursa(job #544233)

Utilizator ChallengeMurtaza Alexandru Challenge Data 1 martie 2011 11:42:46
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <map>

using namespace std;

const char InFile[]="walls.in";
const char OutFile[]="walls.out";
const int MaxN=100111;
const int aint_SIZE=1<<18;

ifstream fin(InFile);
ofstream fout(OutFile);

map< pair<int,int>, int> h; 
int N,M;
long long w[MaxN],tx[MaxN],px;
int ty[MaxN],py;
int aint[aint_SIZE];
int update_pos,update_val;
int query_st,query_dr,query_pos;

void update(int st,int dr,int nod)
{
	if(st==dr)
	{
		aint[nod]=update_val;
		return;
	}
	int l=nod<<1;
	int m=st+((dr-st)>>1);
	if(update_pos<=m)
	{
		update(st,m,l);
	}
	else 
	{
		update(m+1,dr,l|1);
	}
	aint[nod]=max(aint[l],aint[l|1]);
}

void query(int st,int dr,int nod)
{
	if(aint[nod]<py || st>query_dr)
	{
		return;
	}
	if(st==dr)
	{
		query_pos=st;
		return;
	}
	int l=nod<<1;
	int m=st+((dr-st)>>1);
	if(aint[l|1]>=py)
	{
		query(m+1,dr,l|1);
	}
	if(query_pos==-1)
	{
		query(st,m,l);
	}
}

int cautbin(long long x)
{
	int first=1;
	int step=1;
	for(;step<=N;step<<=1);
	for(;step;step>>=1)
	{
		int index=first+step;
		if(index<=N && tx[index]<x)
		{
			first=index;
		}
	}
	if(tx[first]<x)
	{
		return first;
	}
	return -1;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>w[i]>>ty[i];
		tx[i]=w[i]+tx[i-1]+1;
		update_val=ty[i];
		update_pos=i;
		update(1,N,1);
	}
	fin>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>px>>py;
		query_pos=-1;
		query_st=1;
		query_dr=cautbin(px+1);
  		query(1,N,1);
		if(query_pos==-1)
		{
			fout<<"MISS\n";
		}
		else
		{
			int poz=query_pos;
			int &hit=h[make_pair(poz,py)];
			if(++hit==w[poz])
			{
				update_pos=poz;
				update_val=py-1;
				update(1,N,1);
				fout<<"HIT "<<tx[poz]-hit<<" "<<poz<<" YES\n";
			}
			else
			{
				fout<<"HIT "<<tx[poz]-hit<<" "<<poz<<" NO\n";
			}
		}
	}
	fin.close();
	fout.close();
	return 0;
}