Cod sursa(job #579021)

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

const int N=16000;
struct etc{int x,y;} q[N];
int lin[N],col[N],T[N],aux[N],n;
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;
}


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 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);
	v[poz].clear();
	for (unsigned int i=0,j=0;i<v[S].size() || j<v[D].size();)
		if (j>=v[D].size() || i<v[S].size() && v[S][i]<=v[D][j])
			v[poz].push_back(v[S][i++]);
		else
			v[poz].push_back(v[D][j++]);
}

void copy(int a[],int b[])
{
	for (int i=0;i<=b[0];i++)
		a[i]=b[i];
}

void query(int poz,int st,int dr,int x,int y)
{
	if (x<=st && y>=dr)
	{
		copy(aux,T);T[0]=0;
		for (unsigned int i=1,j=0;i<=aux[0] || j<v[poz].size();)
			if (j>=v[poz].size() || i<=aux[0] && aux[i]<=v[poz][j])
				T[++T[0]]=aux[i++];
			else
				T[++T[0]]=v[poz][j++];
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	if (x<=m)
		query(S,st,m,x,y);
	if (m<y)
		query(D,m+1,dr,x,y);
}

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);
		T[0]=0;
		query(1,1,n,x,z);
		out<<bs(T,t)-bs(T,y-1)<<"\n";
	}
	return 0;
}