Pagini recente » Cod sursa (job #1336754) | Cod sursa (job #1135306) | Cod sursa (job #214077) | Cod sursa (job #2485238) | Cod sursa (job #1159554)
#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;
}