Cod sursa(job #1759480)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 19 septembrie 2016 12:02:23
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.56 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ofstream fout( "zoo.out" );
class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while((buffer[cursor] < '0' || buffer[cursor] > '9') && buffer[cursor] != '-') {
                advance();
            }
            int semn = 1;
            if (buffer[cursor] == '-') {
                advance(); semn = -1;
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            n *= semn;
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
} fin ("zoo.in");

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() {
    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";
    }
    fout.close();
    return 0;
}