Cod sursa(job #507725)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 decembrie 2010 17:42:48
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <cstdio>
#include <string>
#include <cstdlib>
#include <algorithm>
#define N 16001
#define common int m=(l+r)>>1, L=n<<1, R=L|1

using namespace std;


int *H[3*N];
int len[3*N];

struct nod
{
	int x,y;

};

nod a[N];
int n;

struct cmp{
	bool operator()(const nod &a, const nod &b)const
	{
		if(a.x < b.x) return 1;
		return 0;
	}
};


void read()
{
	freopen("zoo.in","r",stdin);

	scanf ("%d\n", &n);
	//cit(n);
	for(int i=1; i <= n; ++i)
	{
	//	cit(a[i].x), cit(a[i].y);
		scanf ("%d %d\n", &a[i].x, &a[i].y);
	}
	sort(a+1,a+n+1,cmp());
}

void build(int n,int l, int r)
{
	if(l >= r)
	{
		H[n] = new int[3];
		H[n][len[n]++] = a[l].y;
		return;
	}

	common;

	build(L, l, m);
	build(R, m+1, r);

	int NL=len[L], NR=len[R],i,j;

	H[n]=new int[NL+NR+3];

	for(i=0, j=0; i < NL && j < NR; )
		if(H[L][i] <= H[R][j]) H[n][len[n]++] = H[L][i++];
		else 				  H[n][len[n]++] = H[R][j++];

	for(; i < NL; ++i) H[n][len[n]++] = H[L][i];
	for(; j < NR; ++j) H[n][len[n]++] = H[R][j];

}

inline int bsearch(int a[], int n, int l, int r)
{
	//if(n == 1)
	//	if(a[0] >= l && a[0] <= r) return 1;
	//	else return 0;

	int i, cnt;
	int p=0, q=0;

	for(i=0, cnt=(1<<15); cnt; cnt>>=1)
		if(i + cnt < n)
			if(a[i + cnt] <= r) i += cnt;

	q=i;

	for(i=n-1, cnt=(1<<15); cnt; cnt>>=1)
		if(i - cnt >= 0)
			if(a[i - cnt] >= l) i -= cnt;

	p=i;

	return q-p+1;
}

int x1, y1, x2, y2;

inline int query(int n, int l, int r, int ql, int qr)
{
	if(ql <= l && r <= qr)
	{
		if(y2 < H[n][0] || y1 > H[n][len[n]-1]) return 0;
		if(y1 <= H[n][0] && H[n][len[n]-1] <= y2) return (r-l+1);
		return bsearch(H[n], len[n], y1, y2);
	}

	common;

	int s=0;

	if(ql <= m) s += query(L, l, m, ql, qr);
	if(qr > m)  s += query(R, m+1, r, ql,qr);

	return s;
}



int main()
{

	read();
	build(1, 1, n);

	int m;

	scanf ("%d", &m);
	//cit(m);
	int i, cnt;

	freopen("zoo.out","w",stdout);
	while(m--)
	{
		scanf ("%d %d %d %d\n", &x1, &y1, &x2, &y2);
		//cit(x1); cit(y1); cit(x2); cit(y2);

		if(x2 < a[1].x || x1 > a[n].x) { printf("0\n");}
		else
		{

		for(i=1, cnt=(1<<15); cnt; cnt>>=1)
			if(i + cnt <= n)
				if(a[i + cnt].x <= x2) i += cnt;

		x2=i;

		for(i=n, cnt=(1<<15); cnt; cnt>>=1)
			if(i - cnt >= 1)
				if(a[i - cnt].x >= x1) i -= cnt;

		x1=i;

		printf("%d\n", query(1, 1, n, x1, x2));
		}
	}


	return 0;
}