Cod sursa(job #1513039)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 28 octombrie 2015 22:00:57
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.61 kb
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

FILE *fin = fopen( "zoo.in", "r" ), *fout = fopen( "zoo.out", "w" );

const int nmax = 16000;
const int mmax = 1e5;
const int inf = 2 * 1e9 + 1;
const int valmax = nmax + 2 * mmax + 1;
int n, m, _m, n2x, n2y;
int aib[ valmax + 1 ];
int ans[ mmax + 1 ];
vector< int > x, y;

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 ];

int bsx( int val, int tip ) {
    int sol = 0;
    for( int step = n2x; step > 0; step >>= 1 ) {
        if ( sol + step < ( int )x.size() && x[ sol + step ] <= val ) {
            sol += step;
        }
    }
    if ( tip == 1 && x[ sol ] < val ) {
        ++ sol;
    }
    return sol + 1;
}
int bsy( int val, int tip ) {
    int sol = 0;
    for( int step = n2y; step > 0; step >>= 1 ) {
        if ( sol + step < ( int )y.size() && y[ sol + step ] <= val ) {
            sol += step;
        }
    }
    if ( tip == 1 && y[ sol ] < val ) {
        ++ sol;
    }
    return sol + 1;
}
void normalizare() {
    x.push_back( inf ); x.push_back( -inf );
    y.push_back( inf ); y.push_back( -inf );

    for( int i = 0; i < n; ++ i ) {
        x.push_back( p[ i ].x ); y.push_back( p[ i ].y );
    }
    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( n2x = 1; n2x * 2 <= ( int )x.size(); n2x <<= 1 ) {
    }
    for( n2y = 1; n2y * 2 <= ( int )y.size(); n2y <<= 1 ) {
    }

    for( int i = 0; i < n; ++ i ) {
        p[ i ].x = bsx( p[ i ].x, 0 );
        p[ i ].y = bsy( p[ i ].y, 0 );
    }
    for( int i = 0; i < m; ++ i ) {
        q[ i ].x1 = bsx( q[ i ].x1, 1 );
        q[ i ].y1 = bsy( q[ i ].y1, 1 );
        q[ i ].x2 = bsx( q[ i ].x2, 0 );
        q[ i ].y2 = bsy( q[ i ].y2, 0 );
    }
}
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 );
        }
        if ( v[ i ].ind == 0 ) {
            v[ i ].ind = 0;
        }
        ans[ v[ i ].ind ] += v[ i ].semn * query( v[ i ].y );
    }
}
int main() {
    fscanf( fin, "%d", &n );
    for( int i = 0; i < n; ++ i ) {
        fscanf( fin, "%d%d", &p[ i ].x, &p[ i ].y );
    }
    fscanf( fin, "%d", &m );
    for( int i = 0; i < m; ++ i ) {
        fscanf( fin, "%d%d%d%d", &q[ i ].x1, &q[ i ].y1, &q[ i ].x2, &q[ i ].y2 );
    }
    normalizare();
    split_queries();
    solve();

    for( int i = 0; i < m; ++ i ) {
        fprintf( fout, "%d\n", ans[ i ] );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}