Cod sursa(job #1760168)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 septembrie 2016 13:57:39
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.95 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 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() {
    y.push_back( inf ); y.push_back( -inf );

    for( int i = 0; i < n; ++ i ) {
        y.push_back( p[ i ].y );
    }
    sort( y.begin(), y.end() ); y.erase( unique( y.begin(), y.end() ), y.end() );

    for( n2y = 1; n2y * 2 <= ( int )y.size(); n2y <<= 1 ) {
    }

    for( int i = 0; i < n; ++ i ) {
        p[ i ].y = bsy( p[ i ].y, 0 );
    }
    for( int i = 0; i < m; ++ i ) {
        q[ i ].y1 = bsy( q[ i ].y1, 1 );
        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;
}