Cod sursa(job #2972350)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 29 ianuarie 2023 12:38:22
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#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;
}