Cod sursa(job #309691)

Utilizator blasterzMircea Dima blasterz Data 30 aprilie 2009 22:21:20
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 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
#define dim 8192

using namespace std;
char ax[dim];
int pz;

inline void cit(int &x)
{
	x=0;
	while((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;

	
	int neg=0;
	if(ax[pz] == '-')
	{
		neg=1;
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
	
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
	
	if(neg) x = -x;
}

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

struct nod
{
	int x,y;
	nod(){}; 
	nod(int _x, int _y) { x=_x; y=_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);

	cit(n);	
	for(int i=1; i <= n; ++i)
		cit(a[i].x), cit(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, q;
	
	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;
	
	cit(m);
	int i, cnt;
	
	freopen("zoo.out","w",stdout);	
	while(m--)
	{
		cit(x1); cit(y1); cit(x2); cit(y2);
		
		
		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;
}