Pagini recente » Cod sursa (job #2787149) | Cod sursa (job #1391039) | Cod sursa (job #298164) | Cod sursa (job #2834905) | Cod sursa (job #2972350)
#include <fstream>
#include <map>
#include <set>
using namespace std;
ifstream cin( "zoo.in" );
ofstream cout( "zoo.out" );
const int MAXN = 16'001;
const int MAXM = 1e5 + 2;
struct {
int x, y;
} v[ MAXN ];
struct {
int x1, y1;
int x2, y2;
} q[ MAXM ];
map<int, int> mp;
set<int> s;
int n, m;
short aib[ 2 * MAXN ][ 2 * MAXN ];
void update( int x, int y ) {
for(; x <= n; x += ( x & -x ) )
for( int yy = y; yy <= n; yy += ( yy & -yy ) )
++aib[ x ][ yy ];
}
int query( int x, int y ) {
int sum = 0;
for( ; x > 0; x -= ( x & -x ) )
for( int yy = y; yy > 0; yy -= ( yy & -yy ) )
sum += aib[ x ][ yy ];
return sum;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for( int i = 0; i < n; i++ ) {
cin >> v[ i ].x >> v[ i ].y;
s.insert( v[ i ].x );
s.insert( v[ i ].y );
}
cin >> m;
for( int i = 0; i < m; i++ ) {
cin >> q[ i ].x1 >> q[ i ].y1;
cin >> q[ i ].x2 >> q[ i ].y2;
s.insert( q[ i ].x1 );
s.insert( q[ i ].y1 );
s.insert( q[ i ].x2 );
s.insert( q[ i ].y2 );
}
int no = 1;
for( auto x : s )
mp[ x ] = no++;
for( int i = 0; i < n; i++ )
update( mp[ v[ i ].x ], mp[ v[ i ].y ] );
for( int i = 0; i < m; i++ ) {
int x1 = mp[ q[ i ].x1 ];
int y1 = mp[ q[ i ].y1 ];
int x2 = mp[ q[ i ].x2 ];
int y2 = mp[ q[ i ].y2 ];
cout << query( x2, y2 ) - query( x2, y1 - 1 ) - query( x1 - 1, y2 ) + query( x1 - 1, y1 - 1 ) << '\n';
}
return 0;
}