Cod sursa(job #579342)

Utilizator mihai995mihai995 mihai995 Data 12 aprilie 2011 08:28:17
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=16005;
struct etc{int x,y;} q[N];
int lin[N],col[N],T1[N],T[N],n,rasp,P=1;
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 || a.x==b.x && a.y<b.y;
}

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();
	v.push_back(-5);
	int A=a.size()-1,B=b.size()-1,i,j;
	for (i=j=1;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)
{
	if (st==dr)
	{
		for (v[poz].push_back(-5);q[P].x==st;P++)
			v[poz].push_back(q[P].y);
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	update(S,st,m);
	update(D,m+1,dr);
	inter(v[poz],v[S],v[D]);
}

int bsrc(vector<short int> &v,int x)
{
	int i;unsigned int step=1<<13;
	for (i=0;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);
		if (v[poz][0]>=a)
			rasp++;
		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;
	sort(q+1,q+n+1,cmp);
	for (i=1;i<=n;i++)
		T[i]=q[i].y;
	sort(T+1,T+n+1);
	lin[++lin[0]]=q[1].x;
	col[++col[0]]=T[1];
	for (i=2;i<=n;i++)
	{
		if (q[i].x!=q[i-1].x)
			lin[++lin[0]]=q[i].x;
		if (T[i]!=T[i-1])
			col[++col[0]]=T[i];
	}
	for (i=1;i<=n;i++)
	{
		q[i].x=bs(lin,q[i].x);
		q[i].y=bs(col,q[i].y);
	}
	update(1,1,n);
}

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;
}