Cod sursa(job #579140)

Utilizator mihai995mihai995 mihai995 Data 11 aprilie 2011 21:25:22
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=17000;
struct etc{int x,y;} q[N];
int lin[N],col[N],T[N],n,rasp;
vector<short int> v[3*N];

ifstream in("zoo.in");
ofstream out("zoo.out");

inline bool cmp(const etc &a,const etc &b)
{
	return a.x<b.x;
}

void scrie(vector<short int> &v)
{
	for (unsigned int i=0;i<v.size();i++)
		out<<v[i]<<" ";
	out<<"\n";
}

int bs(int v[],int x)
{
	int i,step=1<<13;
	for (i=0;step;step>>=1)
		if (i+step<=v[0] && v[i+step]<=x)
			i+=step;
	return i;
}

void inter(vector<short int> &v,vector<short int> &a,vector<short int> &b)
{
	v.clear();
	int A=a.size()-1,B=b.size()-1,i,j;
	for (i=j=0;i<=A || j<=B;)
		if (j>B || i<=A && a[i]<b[j])
			v.push_back(a[i++]);
		else
			v.push_back(b[j++]);
}

void update(int poz,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		v[poz].push_back(val);
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	if (x<=m)
		update(S,st,m,x,val);
	else
		update(D,m+1,dr,x,val);
	inter(v[poz],v[S],v[D]);
}

int bsrc(vector<short int> &v,int x)
{
	int i;unsigned int step=1<<13;
	for (i=-1;step;step>>=1)
		if (i+step<v.size() && v[i+step]<=x)
			i+=step;
	return i;
}

void query(int poz,int st,int dr,int x,int y,int a,int b)
{
	if (x<=st && y>=dr)
	{
		rasp+=bsrc(v[poz],b)-bsrc(v[poz],a-1);
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	if (x<=m)
		query(S,st,m,x,y,a,b);
	if (m<y)
		query(D,m+1,dr,x,y,a,b);
}

void normalizare()
{
	int i;
	for (i=1;i<=n;i++)
		T[i]=q[i].x;
	sort(T+1,T+n+1);
	lin[++lin[0]]=T[1];
	for (i=2;i<=n;i++)
		if (T[i]!=T[i-1])
			lin[++lin[0]]=T[i];
	for (i=1;i<=n;i++)
		T[i]=q[i].y;
	sort(T+1,T+n+1);
	col[++col[0]]=T[1];
	for (i=2;i<=n;i++)
		if (T[i]!=T[i-1])
			col[++col[0]]=T[i];
	sort(q+1,q+n+1,cmp);
	for (i=1;i<=n;i++)
		update(1,1,n,bs(lin,q[i].x),bs(col,q[i].y));
}

int main()
{
	int x,y,z,t,times;
	in>>n;
	for (int i=1;i<=n;i++)
		in>>q[i].x>>q[i].y;
	normalizare();
	in>>times;
	while (times--)
	{
		in>>x>>y>>z>>t;
		x=bs(lin,x);z=bs(lin,z);
		y=bs(col,y);t=bs(col,t);
		rasp=0;
		query(1,1,n,x,z,y,t);
		out<<rasp<<"\n";
	}
	return 0;
}