Cod sursa(job #530868)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 8 februarie 2011 16:28:08
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define Nmax 100010
#define st (nod<<1)
#define dr  1 + (nod<<1)
#define Ss A[st].V.size()
#define Sd A[dr].V.size()

using namespace std;

struct punct { int x,y ; } v[Nmax];

struct arb { vector<punct> V ; } A[Nmax<<2];

int n,m,x1,x2,y1,y2,i,a,b,sol;

int cmp ( punct a, punct b ) 
{
	if( a.x == b.x ) return a.y < b.y ; 
	return a.x < b.x ;
}

int lwr ( int val ) 
{
	int r = 0 , s = 1 , d = n , m ;
	
	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 )
		if( v[m].x >= val ) { r = m ; d = m-1 ; }
		else  s = m+1;

	return r;
}

int upr ( int val ) 
{
	int r = 0 , s = 1 , d = n , m ;
	
	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 )
		if( v[m].x <= val ) { r = m ; s = m+1 ; }
		else  d = m-1;

	return r;
}

int lwr1 ( int nod, int size, int val ) 
{
	int r = -1 , s = 0 , d = size , m ;

	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 )
		if( A[nod].V[m].y >= val ) { r = m ; d = m-1 ; }
		else  s = m+1;

	return r;
}

int upr1 ( int nod, int size, int val ) 
{
	int r = -1 , s = 0 , d = size , m ;

	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 ) 
		if( A[nod].V[m].y <= val ) { r = m ; s = m+1 ; }
		else  d = m-1;

	return r;
}

void update( int nod, int s, int d )
{
	if ( s == d )
	{
		A[nod].V.push_back(v[s]);
		return ;
	}
	
	int m = (s+d)>>1;
	
	update(st,s,m);
	update(dr,m+1,d);
	
	int i = 0 , j = 0 ;
	
	while( i < Ss && j < Sd ) 
		if( A[st].V[i].y < A[dr].V[j].y ) 
		{
			A[nod].V.push_back(A[st].V[i]); 
			i++; 
		}
		else
		{
			A[nod].V.push_back(A[dr].V[j]); 
			j++; 
		}
	while( i < Ss )  { A[nod].V.push_back(A[st].V[i]);  i++; } 
	while( j < Sd )  { A[nod].V.push_back(A[dr].V[j]);  j++; } 
}	

void query( int nod, int s, int d ) 
{
	if( a <= s && d <= b ) 
	{
		int ls = lwr1 ( nod , A[nod].V.size()-1, y1 ) ;
		int ld = upr1 ( nod , A[nod].V.size()-1, y2 ) ;
		
		if( ls >= 0 && ld >=0 ) 
			sol = sol + ld - ls + 1 ;
		
		return ;
	}
	
	int m = (s+d)>>1;
	
	if( a <= m ) query(st,s,m);
	if( m < b  ) query(dr,m+1,d);
}

int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	
	scanf("%d",&n);
	
	for( i = 1 ; i <= n ; i++ )
		scanf("%d %d",&v[i].x,&v[i].y) ;
	
	sort( v+1, v+n+1, cmp );
	
	update(1,1,n);
	
	scanf("%d",&m);
	
	for( i = 1 ; i <= m ; i++ )
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		
		sol = 0 ;
		
		a = lwr(x1) ; b = upr(x2);
		
		if( a && b ) 
			query(1,1,n);
		
		printf("%d\n",sol);
	}
	
	return 0;
}