Cod sursa(job #2064627)

Utilizator robx12lnLinca Robert robx12ln Data 12 noiembrie 2017 17:02:48
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include<fstream>
#include<algorithm>
#define DIM 16005
#define LOG 15
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int aux[DIM], N, M;
int Arb[LOG][DIM];
struct Point{
    int x, y;
} P[DIM];
inline int cmp( const Point &a, const Point &b ){
    if( a.x == b.x )
        return a.y < b.y;
    return a.x < b.x;
}
void build( int Niv, int st, int dr ){
    if( st > dr )
        return;
    if( st == dr )
        Arb[Niv][st] = P[st].y;
    else{
        int mid = ( st + dr ) >> 1;
        build( Niv + 1, st, mid );
        build( Niv + 1, mid + 1, dr );
        for( int i = 1, j = mid + 1, pos = st; i <= mid || j <= dr; ){
            if( j > dr || ( i <= mid && Arb[Niv + 1][i] <= Arb[Niv + 1][j] ) )
                Arb[Niv][pos++] = Arb[Niv + 1][i++];
            else
                Arb[Niv][pos++] = Arb[Niv + 1][j++];
        }
    }
}
inline int get_posArb1( int Niv, int p, int u, int x ){
    while( p <= u ){
        int m = ( p + u ) >> 1;
        if( Arb[Niv][m] < x )
            p = m + 1;
        else
            u = m - 1;
    }
    return u;
}
inline int get_posArb2( int Niv, int p, int u, int x ){
    while( p <= u ){
        int m = ( p + u ) >> 1;
        if( Arb[Niv][m] <= x )
            p = m + 1;
        else
            u = m - 1;
    }
    return u;
}
int query( int Niv, int st, int dr, int X1, int X2, int Y1, int Y2 ){
    if( X1 > X2 )
        return 0;
    int sol = 0;
    if( X1 <= st && dr <= X2 ){
        int p1 = get_posArb1( Niv, st, dr, Y1 ) + 1;
        int p2 = get_posArb2( Niv, st, dr, Y2 );
        if( p1 > p2 )
            return 0;
        else
            return p2 - p1 + 1;
    }else{
        int mid = ( st + dr ) / 2;
        if( X1 <= mid )
            sol += query( Niv + 1, st, mid, X1, X2, Y1, Y2 );
        if( X2 > mid )
            sol += query( Niv + 1, mid + 1, dr, X1, X2, Y1, Y2 );
    }
    return sol;
}
inline int get_pos1( int x, int a[], int dr ){
    int st = 1;
    while( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if( a[mid] < x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}
inline int get_pos2( int x, int a[], int dr ){
    int st = 1;
    while( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if( a[mid] <= x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ )
        fin >> P[i].x >> P[i].y;
    sort( P, P + N, cmp );
    for( int i = 1; i <= N; i++ )
        aux[i] = P[i].x;
    build( 0, 1, N );
    fin >> M;
    for( int i = 1; i <= M; i++ ){
        int X1, X2, Y1, Y2;
        fin >> X1 >> Y1 >> X2 >> Y2;
        X1 = get_pos1( X1, aux, N ) + 1;
        X2 = get_pos2( X2, aux, N );
        fout << query( 0, 1, N, X1, X2, Y1, Y2 ) << "\n";
    }
    return 0;
}