Cod sursa(job #204694)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 26 august 2008 14:58:09
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<stdio.h>
#define N 1607
long long n,i,j,m,x1,x2,y1,y2,b[N],x,y,h[33][N];
struct zoo{
	long long x,y;
}a[N];
long long search(long long v[],long long l,long long r,long long e){
	long long poz,p;
	for(p=1;p<=(r-l+1);p<<=1);
	for(poz=l-1;p;p>>=1)
		if(p+poz <=r)
			if(v[poz+p]<=e)
			poz+=p;
		return poz;
}
long long half(long long st,long long dr){
	zoo aux;
	long 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 sort(long long st,long long dr){
	long long mij=half(st,dr);
	if(mij+1<dr)
		sort(mij+1,dr);
	if(mij-1>st)
		sort(st,mij-1);
}
void funct(long long nv,long long l,long long r){
	if(l==r){
		h[nv][l]=a[l].y;
		return;
	}
	long long mij=(l+r)>>1,i,j,k;
	if(mij>=l)
		funct(nv+1,l,mij);
	if(mij+1<=r)
		funct(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++];
}
long long solv(long long nv,long long st,long long dr){
	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;
		return search(h[nv],st,dr,y2)-search(h[nv],st,dr,y1-1);
	}
	long long t = 0,mij;
	mij = (st+dr)>>1;
	if(mij >= x)
		t+=solv(nv+1,st,mij);
	if(mij+1<=y)
		t+=solv(nv+1,mij+1,dr);
	return t;
}
int main(){
	freopen("zoo.in","r",stdin);   
    freopen("zoo.out","w",stdout);
	scanf("%lld",&n);
	for(i=1;i<=n;++i)
		scanf("%lld%lld",&a[i].x,&a[i].y);
	sort(1,n);
	for(i=1;i<=n;++i)
		b[i]=a[i].x;
    funct(0,1,n);
	scanf("%lld",&m);
	for(i=1;i<=m;++i){
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		x=search(b,1,n,x1-1)+1;
		y=search(b,1,n,x2);
		printf("%lld\n",solv(0,1,n));
	}
	return 0;
}