Cod sursa(job #615718)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2011 17:20:45
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 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 int cblower(int v[], int size, int val)
{
	int st=0;
	int dr=size-1;
	int sol=-1;
	while(st<dr)
	{
		int mid=st+((dr-st)>>1);
		if(v[mid]<=val)
		{
			sol=mid;
			st=mid+1;
		}
		else
		{
			dr=mid-1;
		}
	}
	if(v[sol]<val)
	{
		++sol;
	}
	return sol;
}

inline int cbupper(int v[], int size, int val)
{
	int st=0;
	int dr=size-1;
	int sol=-1;
	while(st<dr)
	{
		int mid=st+((dr-st)>>1);
		if(val<=v[mid])
		{
			sol=mid;
			dr=mid-1;
		}
		else
		{
			st=mid+1;
		}
	}
	if(val<v[sol])
	{
		--sol;
	}
	return sol;
}

inline void cauta(int nod)
{
	sol+=min(N,cblower(&aint[nod].y[0],aint[nod].y.size(),ymax)+1)-max(1,cbupper(&aint[nod].y[0],aint[nod].y.size(),ymin)+1)+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=0;i<N;++i)
	{
		v[i]=p[i+1].x;
	}

	init(1,1,N);

	fin>>M;
	for(register int i=1;i<=M;++i)
	{
		sol=0;
		fin>>xmin>>ymin>>xmax>>ymax;
		pst=max(1,cbupper(v,N,xmin)+1);
		pdr=min(N,cblower(v,N,xmax)+1);
		if(1<=pst && pst<=pdr && pdr<=N)
		{
			query(1,1,N);
		}
		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}