Cod sursa(job #183369)

Utilizator amadaeusLucian Boca amadaeus Data 21 aprilie 2008 23:52:11
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define X first
#define Y second
#define ALL(C) C.begin(), C.end()
#define TR(C,i) \
	for( typeof(C.begin()) i = C.begin(); i != C.end(); i++ )

#define BSZ (1<<16)
#define NX (1<<16)

typedef pair< int, int > point;

vector< point > v;
int N, M, x1, x2, y1, y2;

vector< int > A[ NX ];

char buf[ BSZ ];
int p = BSZ - 1;

int get2() {
	int x;
	scanf( "%d", &x );
	return x;
}

int get() {
	int x = 0, sgn = 1;

	while( buf[p] < '0' || buf[p] > '9' ) {
		if( buf[p] == '-' )
			sgn = -1;
		if( ++p == BSZ )
			fread( buf, 1, BSZ, stdin ), p = 0;
	}

	while( buf[p] >= '0' && buf[p] <= '9' ) {
		x = x*10 + buf[p] - '0';
		if( ++p == BSZ )
			fread( buf, 1, BSZ, stdin ), p = 0;
	}

	return sgn * x;
}

void build( int n, int l, int r ) {
	if( l == r ) {
		A[n].pb( v[l].Y );
		return;
	}

	int m = (l+r) >> 1, nl = n<<1, nr = nl+1;

	build( nl, l, m );
	build( nr, m+1, r );
	A[n].resize( A[nl].size() + A[nr].size() );
	merge( ALL( A[nl] ), ALL( A[nr] ), A[n].begin() );
}

int query( int n, int l, int r ) {
	if( x2 < v[l].X || x1 > v[r].X )
		return 0;
	if( x1 <= v[l].X && v[r].X <= x2 )
		return (int) ( upper_bound( ALL(A[n]), y2 ) - lower_bound( ALL(A[n]), y1 ) );

	int res = 0, m = (l+r) >> 1;

	if( v[m].X >= x1 )
		res += query( n<<1, l, m );
	if( v[m].X < x2 )
		res += query( (n<<1)+1, m+1, r );
	return res;
}

void cit() {
	int i, x, y;
	
	N = get();
	for( i = 1; i <= N; i++ ) {
		x = get();
		y = get();
		v.pb( point( x, y ) );
	}

	sort( v.begin(), v.end() );
	
	build( 1, 0, N-1 );

	M = get();
	while( M-- ) {
		x1 = get();
		y1 = get();
		x2 = get();
		y2 = get();

		printf( "%d\n", query( 1, 0, N-1 ) );
	}
}

int main(){
	freopen( "zoo.in", "r", stdin );
	freopen( "zoo.out", "w", stdout );

	cit();

	return 0;
}