Cod sursa(job #1159554)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 29 martie 2014 18:23:16
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define max_n 16010
#define inf 2000000100
#define max_s 10000000

//ifstream f("zoo.in");
//ofstream g("zoo.out");

FILE*f = fopen( "zoo.in" , "r" );
FILE*g = fopen( "zoo.out" , "w" );

struct point{
	int x , y;
}V[max_n];

int n , m , x1 , y11 , x2 , y22 , a , b , k , v;
vector<int>Arb[3*max_n];
char sir[max_s];

int get_nr( int &a ){
	a = 0; int sgn = 1;
	while( (sir[k] < '0' || sir[k] > '9') && sir[k] != '-' )
		k++;
	if( sir[k] == '-' ){
		sgn = -1;
		k++;
	}
	while( sir[k] >= '0' && sir[k] <= '9' ){
		a = a*10 + sir[k] - '0';
		k++;
	}
	a *= sgn;
}

bool cmp( point a , point b ){
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}

void read(){

	fread( sir , 1 , max_s , f );

	get_nr(n);

	V[0].x = V[0].y = -inf;
	for( int i = 1 ; i <= n ; i++ )
		get_nr(V[i].x) , get_nr(V[i].y);
	sort( V + 1 , V + n + 1 , cmp );
}

void form_arb( int nod , int st , int dr ){

	if( st == dr ){
		Arb[nod].push_back( -inf );
		Arb[nod].push_back( V[st].y );
		return;
	}

	int mid = ( st + dr ) / 2;

	form_arb(2*nod , st , mid);
	form_arb(2*nod+1 , mid+1 , dr);

	Arb[nod].push_back( -inf );
	unsigned int p1 = 1 , p2 = 1;
	int nd1 = 2*nod , nd2 = 2*nod+1;

	while( p1 < Arb[nd1].size() && p2 < Arb[nd2].size() ){
		if( Arb[nd1][p1] > Arb[nd2][p2] ){
			Arb[nod].push_back( Arb[nd2][p2] );
			p2++;
		}
		else{
			Arb[nod].push_back( Arb[nd1][p1] );
			p1++;
		}
	}

	while( p1 < Arb[nd1].size() ){
		Arb[nod].push_back( Arb[nd1][p1] );
		p1++;
	}
	while( p2 < Arb[nd2].size() ){
		Arb[nod].push_back( Arb[nd2][p2] );
		p2++;
	}

}

int search(){

	int step , i;

	for( step = 1 ; step < n ; step <<= 1 );

	for( i = 0 ; step ; step >>= 1 )
		if( (i + step) <= n && V[i+step].x <= v )
			i += step;
	return i;

}

int search1( int nod ){

	int step , i;
	int L = Arb[nod].size() - 1;

	for( step = 1 ; step < L ; step <<= 1 );

	for( i = 0 ; step ; step >>= 1 )
		if( (i + step) <= L && Arb[nod][i+step] <= v )
			i += step;
	return i;

}

int querry( int nod , int st , int dr ){
	if( a <= st && dr <= b ){

		v = y11 - 1;
		unsigned int p1 = search1( nod );

		v = y22;
		unsigned int p2 = search1( nod );

		if( Arb[nod][p1] < y11 )
			p1++;
		if( p2 == 0 || p1 > n )
			return 0;

		return p2 - p1 + 1;
	}

	int mid = (st + dr) / 2;
	int v1 = 0 , v2 = 0;

	if( a <= mid )
		v1 = querry( 2*nod , st , mid );
	if( b > mid )
		v2 = querry( 2*nod+1 , mid+1 , dr );

	return v1 + v2;
}

void solve(){

	get_nr(m);

	for( ; m ; m-- ){

		get_nr(x1);		get_nr(y11);
		get_nr(x2);		get_nr(y22);

		v = x1 - 1 ;
		a = search();

		v = x2;
		b = search();

		if( V[a].x < x1 )
			a++;
		if( a > n || b == 0 ){
			fprintf( g , "0\n" );
			continue;
		}

		fprintf(g , "%d\n" , querry( 1 , 1 , n ));
	}

}

int main(){

	read();

	form_arb( 1 , 1 , n );

	solve();

	return 0;
}