Cod sursa(job #742099)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 28 aprilie 2012 15:05:28
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
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,poz1,poz2,st,dr,mij,ns,poz,aux,semn;
	char s[55];
	ifstream fin("zoo.in");
	ofstream fout("zoo.out");
	
	//fin>>n;
	fin.getline(s,55);
	ns=strlen(s);
	poz=0;
	while(poz<ns)
	{
		n=n*10+s[poz]-'0';
		poz++;
	}
	//
	for(i=1;i<=n;i++)
	{
		//fin>>P[i].x>>P[i].y;
		fin.getline(s,55);
		ns=strlen(s);
		poz=0;
		aux=0;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(s[poz]!=' ')
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		P[i].x=semn*aux;
		aux=0;
		poz++;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(poz<ns)
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		P[i].y=semn*aux;
		//
	}
	
	sort(P+1,P+n+1,SortareX);
	Construire_ArboreIntervale(1,1,n);
	
	//fin>>Q;
	fin.getline(s,55);
	ns=strlen(s);
	poz=0;
	while(poz<ns)
	{
		Q=Q*10+s[poz]-'0';
		poz++;
	}
	//
	for(i=1;i<=Q;i++)
	{
		//fin>>xmin>>ymin>>xmax>>ymax;
		fin.getline(s,55);
		ns=strlen(s);
		poz=0;
		aux=0;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(s[poz]!=' ')
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		xmin=semn*aux;
		aux=0;
		poz++;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(s[poz]!=' ')
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		ymin=semn*aux;
		aux=0;
		poz++;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(s[poz]!=' ')
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		xmax=semn*aux;
		aux=0;
		poz++;
		if(s[poz]=='-')
		{
			semn=-1;
			poz++;
		}
		else
			semn=1;
		while(poz<ns)
		{
			aux=aux*10+s[poz]-'0';
			poz++;
		}
		ymax=semn*aux;
		//
		sol=0;
		st=1;
		dr=n;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			if(P[mij].x>=xmin)
				dr=mij-1;
			else
				st=mij+1;
		}
		poz1=st;
		st=1;
		dr=n;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			if(P[mij].x<=xmax)
				st=mij+1;
			else
				dr=mij-1;
		}
		poz2=dr;
		if(1<=poz1 && poz1<=poz2 && poz2<=n)
			Query(1,1,n);
		else
			sol=0;
		fout<<sol<<"\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}