Pagini recente » Cod sursa (job #2989915) | Cod sursa (job #90120) | Cod sursa (job #1397446) | Cod sursa (job #1987970) | Cod sursa (job #1159503)
#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 , y1 , x2 , y2 , 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] , y1 - 1 );
if( V[Arb[nod][p1]].y < y1 )
p1++;
unsigned int p2 = search1( Arb[nod] , y2 );
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>>y1>>x2>>y2;
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;
}