Cod sursa(job #615724)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2011 17:51:46
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const char InFile[]="zoo.in";
const char OutFile[]="zoo.out";
const int MaxN=16111;
const int AINT_SIZE=MaxN<<2;

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

struct point
{
	point(int x=0, int y=0):x(x),y(y){}
	int x,y;
};

struct cmp_point_x
{
	inline bool operator() (const point &a, const point &b)
	{
		return a.x<b.x;
	}
};

struct aint_node
{
	vector<int> y;
};

int N,M,sol,xmin,ymin,xmax,ymax,pst,pdr,v[MaxN];
point p[MaxN];
aint_node aint[AINT_SIZE];

inline void cauta(int nod)
{
	int p=0,u=aint[nod].y.size()-1;
	while(p<=u)
	{
		int m=p+((u-p)>>1);
		if(aint[nod].y[m]>=ymin)
		{
			u=m-1;
		}
		else
		{
			p=m+1;
		}
	}
	int st=p;
	p=0,u=aint[nod].y.size()-1;
	while(p<=u)
	{
		int m=p+((u-p)>>1);
		if(aint[nod].y[m]<=ymax)
		{
			p=m+1;
		}
		else
		{
			u=m-1;
		}
	}
	int dr=u;
	sol+=dr-st+1;
}

void init(int nod, int st, int dr)
{
	if(st==dr)
	{
		aint[nod].y.push_back(p[st].y);
		return;
	}

	int l=nod<<1;
	int mid=st+((dr-st)>>1);

	init(l,st,mid);
	init(l+1,mid+1,dr);

	unsigned int ind1=0;
	unsigned int ind2=0;
	while(ind1<aint[l].y.size() && ind2<aint[l+1].y.size())
	{
		if(aint[l].y[ind1]<aint[l+1].y[ind2])
		{
			aint[nod].y.push_back(aint[l].y[ind1]);
			++ind1;
		}
		else
		{
			aint[nod].y.push_back(aint[l+1].y[ind2]);
			++ind2;
		}
	}
	while(ind1<aint[l].y.size())
	{
		aint[nod].y.push_back(aint[l].y[ind1]);
		++ind1;
	}
	while(ind2<aint[l+1].y.size())
	{
		aint[nod].y.push_back(aint[l+1].y[ind2]);
		++ind2;
	}
}

void query(int nod, int st, int dr)
{
	if(pst<=st && dr<=pdr)
	{
		cauta(nod);
		return;
	}

	int mid=st+((dr-st)>>1);
	nod<<=1;
	if(pst<=mid)
	{
		query(nod,st,mid);
	}
	if(mid<pdr)
	{
		query(nod+1,mid+1,dr);
	}
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
	}

	sort(p+1,p+1+N,cmp_point_x());
	for(register int i=1;i<=N;++i)
	{
		v[i]=p[i].x;
	}

	init(1,1,N);

	fin>>M;
	for(register int i=1;i<=M;++i)
	{
		sol=0;
		fin>>xmin>>ymin>>xmax>>ymax;
		int p=1,u=N;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(v[m]>=xmin)
			{
				u=m-1;
			}
			else
			{
				p=m+1;
			}
		}
		pst=p;
		p=1;u=N;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(v[m]<=xmax)
			{
				p=m+1;
			}
			else
			{
				u=m-1;
			}
		}
		pdr=u;
		if(1<=pst && pst<=pdr && pdr<=N)
		{
			query(1,1,N);
		}
		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}