Cod sursa(job #38947)

Utilizator DorinOltean Dorin Dorin Data 26 martie 2007 11:54:59
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
# include<stdio.h>

# define input "zoo.in"
# define output "zoo.out"

# define max 1024001

long n,i,j,m,x1,x2,y1,y2,b[max],x,y,h[33][max];

struct kkt
{
	long x,y;
}a[max];


long divide(long st,long dr)
{
	kkt aux;
	long c;
	aux = a[st];
	c=a[st].x;
	while(st < dr)
	{
		while(st < dr && a[dr].x >= c)dr--;
		a[st] = a[dr];
		while(st < dr && a[st].x <= c)st++;
		a[dr] = a[st];
	}
	a[st] = aux;
	return st;
}

void build(long nv,long l,long r)
{
	if(l == r)
		{h[nv][l] = a[l].y;return;}

	long mij = (l+r)>>1,i,j,k;
	build(nv+1,l,mij);
	build(nv+1,mij+1,r);
	for(i = l,j=mij+1,k=l;i<=mij&&j<=r;)
		if(h[nv+1][i] < h[nv+1][j])
			h[nv][k++] = h[nv+1][i++];
		else
			h[nv][k++] = h[nv+1][j++];
	while(i<=mij)
		h[nv][k++] = h[nv+1][i++];
	while(j<=r)
		h[nv][k++] = h[nv+1][j++];
}

void qsort(long st,long dr)
{
	long mij =divide(st,dr);
	if(mij+1 < dr)qsort(mij+1,dr);
	if(mij-1 > st)qsort(st,mij-1);
}
long search(long v[],long l,long r,long e)
{
	long poz,step;
	for(step=1;step<(r-l+1);step<<=1);
	for(poz = l-1;step;step>>=1)
		if(step+poz <=r && v[poz + step] <= e)
			poz+=step;
	return poz;
}

long det_nr(long nv,long st,long dr)
{
	long t = 0,mij;
	if(x <= st && dr <= y)
	{
		if(y2 < h[nv][st] || y1 > h[nv][dr])
			return 0;
		if(y1 < h[nv][st] && y2 > h[nv][dr])
			return dr-st+1;
		t=search(h[nv],st,dr,y2)-search(h[nv],st,dr,y1-1);
	}
	else
	{
		mij = (st+dr)>>1;
		if(mij >= x)
			t+=det_nr(nv+1,st,mij);
		if(mij+1<=y)
			t+=det_nr(nv+1,mij+1,dr);
	}
	return t;
}

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);

	scanf("%ld",&n);
	for(i = 1;i<=n;i++)
		scanf("%ld%ld",&a[i].x,&a[i].y);

	qsort(1,n);

	for(i= 1;i<=n;i++)
		b[i] = a[i].x;

	build(0,1,n);
	
	scanf("%ld",&m);

	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2);
		x=search(b,1,n,x1-1)+1;
		y=search(b,1,n,x2);
		printf("%ld\n",det_nr(0,1,n));
	}

	return 0;
}