Cod sursa(job #1513050)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 28 octombrie 2015 22:12:45
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.03 kb
#include<fstream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

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

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;
string s; string::iterator it;

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 read_int( int &k ) {
    int semn = 1;
    k = 0;
    while ( it != s.end() && *it != '-' &&  ( *it < '0' || *it > '9' ) ) {
        ++ it;
    }
    if ( it != s.end() && *it == '-' ) {
        semn = -1; ++ it;
    }
    while ( it != s.end() && *it >= '0' && *it <= '9' ) {
        k = k * 10 + *it - '0';
        ++ it;
    }
    k *= semn;
}
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() {
    getline( fin, s, ( char )0 ); it = s.begin();

    read_int( n );
    for( int i = 0; i < n; ++ i ) {
        read_int( p[ i ].x ); read_int( p[ i ].y );
    }
    read_int( m );
    for( int i = 0; i < m; ++ i ) {
        read_int( q[ i ].x1 ); read_int( q[ i ]. y1 );
        read_int( q[ i ].x2 ); read_int( q[ i ].y2 );
    }
    normalizare();
    split_queries();
    solve();

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