Cod sursa(job #544255)

Utilizator ChallengeMurtaza Alexandru Challenge Data 1 martie 2011 12:18:32
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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);

struct vector2d{int x,y;};

map< pair<int,int>, int> h;
vector2d v[MaxN];
int N,M;
int aint[aint_SIZE];
long long poz[MaxN],px,py;
int update_val,update_pos;
int 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(px<poz[st] || aint[nod]<py)
	{
		return;
	}
	if(st==dr)
	{
		query_pos=st;
		return;
	}
	int l=nod<<1;
	int m=st+((dr-st)>>1);
	query(m+1,dr,l|1);
	if(!query_pos)
	{
		query(st,m,l);
	}
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>v[i].x>>v[i].y;
		poz[i]=1+poz[i-1]+v[i-1].x;
		update_pos=i;
		update_val=v[i].y;
		update(1,N,1);
	}
	fin>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>px>>py;
		query_pos=0;
		query(1,N,1);
		if(query_pos)
		{
			fout<<"HIT ";
			pair<int,int> cell=make_pair(query_pos,py);
			++h[cell];
			fout<<poz[query_pos]+v[query_pos].x-h[cell]<<" "<<query_pos;
			if(h[cell]==v[query_pos].x)
			{
				update_pos=query_pos;
				update_val=py-1;
				update(1,N,1);
				fout<<" YES\n";
			}
			else
			{
				fout<<" NO\n";
			}
		}
		else
		{
			fout<<"MISS\n";
		}
	}
	fin.close();
	fout.close();
	return 0;
}