Pagini recente » Cod sursa (job #2243935) | Cod sursa (job #2935065) | Cod sursa (job #64312) | Cod sursa (job #3155491) | Cod sursa (job #2972413)
#include <fstream>
#include <vector>
#define x first
#define y second
#define z( x ) ( ( x ) & ( -x ) )
using namespace std;
int const MAX = 16'002;
ifstream cin( "zoo.in" );
ofstream cout( "zoo.out" );
int n, q, a, b, c, d;
int x[ MAX ];
vector<int> t[ MAX ];
pair<int, int> p[ MAX ];
void add( int idx, int val ) {
for( int i = idx; i <= n; i += z( i ) )
t[ i ].push_back( val );
}
int sum( int p, int st, int dr ) {
int rez = 0;
for( int i = p; i; i -= z( i ) )
rez += ( upper_bound( t[ i ].begin(), t[ i ].end(), dr ) - lower_bound( t[ i ].begin(), t[ i ].end(), st ) );
return rez;
}
int query( int from, int to, int st, int dr ) {
return sum( to, st, dr ) - sum( from - 1, st, dr );
}
int main()
{
cin >> n;
for( int i = 1; i <= n; i++ ) {
cin >> p[ i ].x >> p[ i ].y;
x[ i ] = p[ i ].x;
}
sort( p + 1, p + 1 + n );
sort( x + 1, x + 1 + n );
for( int i = 1; i <= n; i++ )
add( i, p[ i ].y );
for( int i = 1; i <= n; i++ )
sort( t[ i ].begin(), t[ i ].end() );
cin >> q;
for( int i = 1; i <= q; i++ ) {
cin >> a >> b >> c >> d;
int x1 = ( lower_bound( x + 1, x + 1 + n, a ) - x );
int x2 = ( upper_bound( x + 1, x + 1 + n, c ) - x );
cout << query( x1, x2 - 1, b, d ) << '\n';
}
return 0;
}