Cod sursa(job #1159505)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 29 martie 2014 17:41:03
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

#define max_n 16010
#define inf 2000000100

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

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

int n , m , x1 , y11 , x2 , y22 , p1 , p2;
vector<int>Arb[3*max_n];

bool cmp( point a , point b ){
	return a.x < b.x;
}

void read(){
	f>>n;
	V[0].x = V[0].y = -inf;
	for( int i = 1 ; i <= n ; i++ )
		f>>V[i].x>>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(0);
		Arb[nod].push_back( st );
		return;
	}

	int mid = ( st + dr ) / 2;

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

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

	while( p1 < Arb[nd1].size() && p2 < Arb[nd2].size() ){
		if( V[Arb[nd1][p1]].y > V[Arb[nd2][p2]].y ){
			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 v ){

	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( vector<int> A , int v ){

	int step , i;
	int L = A.size() - 1;

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

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

}

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

		unsigned int p1 = search1( Arb[nod] , y11 - 1 );
		if( V[Arb[nod][p1]].y < y11 )
			p1++;
		unsigned int p2 = search1( Arb[nod] , y22 );
		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 , a , b );
	if( b > mid )
		v2 = querry( 2*nod+1 , mid+1 , dr , a , b );

	return v1 + v2;
}

void solve(){

	f>>m;

	for( ; m ; m-- ){

		f>>x1>>y11>>x2>>y22;

		p1 = search( x1 - 1 );
		if( V[p1].x < x1 )
			p1++;
		p2 = search( x2 );
		if( p1 > n || p2 == 0 ){
			g<<"0\n";
			continue;
		}

		g<<querry( 1 , 1 , n , p1 , p2 )<<"\n";
	}

}

int main(){

	read();

	form_arb( 1 , 1 , n );

	solve();

	return 0;
}