Cod sursa(job #2972413)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 29 ianuarie 2023 14:08:54
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
}