Cod sursa(job #742091)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 28 aprilie 2012 14:52:59
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int n,Q,xmin,ymin,xmax,ymax,sol;
struct Punct{int x,y;};
Punct P[17000];
struct Nod{vector <int> Y;};
Nod Aint[33000];

inline bool SortareX(Punct A,Punct B)
{
	return A.x<B.x;
}

inline void Construire_ArboreIntervale(int nod,int st,int dr)
{
	if(st==dr)
	{
		Aint[nod].Y.push_back(P[st].y);
		return;
	}
	int mij=(st+dr)/2,fiu=2*nod;
	Construire_ArboreIntervale(fiu,st,mij);
	Construire_ArboreIntervale(fiu+1,mij+1,dr);
	Aint[nod].Y.resize(dr-st+1);
	merge(Aint[fiu].Y.begin(),Aint[fiu].Y.end(),Aint[fiu+1].Y.begin(),Aint[fiu+1].Y.end(),Aint[nod].Y.begin());
}

inline void Query(int nod,int st,int dr)
{
	if(xmin<=P[st].x && P[dr].x<=xmax)
	{
		int poz1,poz2;
		//poz1=lower_bound(Aint[nod].Y.begin(),Aint[nod].Y.end(),ymin)-Aint[nod].Y.begin();
		//poz2=upper_bound(Aint[nod].Y.begin(),Aint[nod].Y.end(),ymax)-Aint[nod].Y.begin();
		sol+=(poz2-poz1);
		return;
	}
	int mij=(st+dr)/2,fiu=2*nod;
	if(xmin<=P[mij].x)
		Query(fiu,st,mij);
	if(P[mij+1].x<=xmax)
		Query(fiu+1,mij+1,dr);
}

int main()
{
	int i;
	ifstream fin("zoo.in");
	ofstream fout("zoo.out");
	
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>P[i].x>>P[i].y;
	
	sort(P+1,P+n+1,SortareX);
	Construire_ArboreIntervale(1,1,n);
	
	fin>>Q;
	for(i=1;i<=Q;i++)
	{
		fin>>xmin>>ymin>>xmax>>ymax;
		sol=0;
		Query(1,1,n);
		fout<<sol<<"\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}