Cod sursa(job #1512950)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 28 octombrie 2015 20:09:03
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream fin( "zoo.in" ); ofstream fout( "zoo.out" );

const int nmax = 16000;
const int mmax = 1e5;
const int valmax = nmax + mmax + 1;
int n, m, _m;
int aib[ valmax + 1 ];
int ans[ mmax + 1 ];

struct punct{
    int x, y;

    inline bool operator < ( const punct &a ) const {
        return ( x < a.x );
    }
} p[ nmax + 1 ];

struct big_query{
    int x1, x2, y1, y2;
} q[ mmax + 1 ];

struct small_query{
    int x, y, ind, semn;

    small_query() {}
    small_query( int _x, int _y, int _ind, int _semn ) : x( _x ), y( _y ), ind( _ind ), semn( _semn ) {}

    inline bool operator < ( const small_query &a ) const {
        return ( x < a.x );
    }
} v[ 4 * mmax + 1 ];

void normalizare() {
    vector< int > x, y;
    for( int i = 0; i < n; ++ i ) {
        x.push_back( p[ i ].x ); y.push_back( p[ i ].y );
    }
    for( int i = 0; i < m; ++ i ) {
        x.push_back( q[ i ].x1 ); y.push_back( q[ i ].y1 );
        x.push_back( q[ i ].x2 ); y.push_back( q[ i ].y2 );
    }
    sort( x.begin(), x.end() ); x.erase( unique( x.begin(), x.end() ), x.end() );
    sort( y.begin(), y.end() ); y.erase( unique( y.begin(), y.end() ), y.end() );

    for( int i = 0; i < n; ++ i ) {
        p[ i ].x = lower_bound( x.begin(), x.end(), p[ i ].x ) - x.begin() + 1;
        p[ i ].y = lower_bound( y.begin(), y.end(), p[ i ].y ) - y.begin() + 1;
    }
    for( int i = 0; i < m; ++ i ) {
        q[ i ].x1 = lower_bound( x.begin(), x.end(), q[ i ].x1 ) - x.begin() + 1;
        q[ i ].y1 = lower_bound( y.begin(), y.end(), q[ i ].y1 ) - y.begin() + 1;
        q[ i ].x2 = lower_bound( x.begin(), x.end(), q[ i ].x2 ) - x.begin() + 1;
        q[ i ].y2 = lower_bound( y.begin(), y.end(), q[ i ].y2 ) - y.begin() + 1;
    }
}
void split_queries() {
    _m = 0;
    for( int i = 0; i < m; ++ i ) {
        v[ _m ++ ] = small_query( q[ i ].x2, q[ i ].y2, i, +1 );
        v[ _m ++ ] = small_query( q[ i ].x2, q[ i ].y1 - 1, i, -1 );
        v[ _m ++ ] = small_query( q[ i ].x1 - 1, q[ i ].y2, i, -1 );
        v[ _m ++ ] = small_query( q[ i ].x1 - 1, q[ i ].y1 - 1, i, +1 );
    }
}
void update( int pos ) {
    for( int i = pos; i <= valmax; i += (i & -i) ) {
        ++ aib[ i ];
    }
}
int query( int pos ) {
    int sol = 0;
    for( int i = pos; i > 0; i -= (i & -i) ) {
        sol += aib[ i ];
    }
    return sol;
}
void solve() {
    sort( v, v + _m );
    sort( p, p + n );
    int ii = 0;
    for( int i = 0; i < _m; ++ i ) {
        while ( ii < n && p[ ii ].x <= v[ i ].x ) {
            update( p[ ii ++ ].y );
        }
        ans[ v[ i ].ind ] += v[ i ].semn * query( v[ i ].y );
    }
}
int main() {
    fin >> n;
    for( int i = 0; i < n; ++ i ) {
        fin >> p[ i ].x >> p[ i ].y;
    }
    fin >> m;
    for( int i = 0; i < m; ++ i ) {
        fin >> q[ i ].x1 >> q[ i ].y1 >> q[ i ].x2 >> q[ i ].y2;
    }
    normalizare();
    split_queries();
    solve();

    for( int i = 0; i < m; ++ i ) {
        fout << ans[ i ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}