Cod sursa(job #2064693)

Utilizator robx12lnLinca Robert robx12ln Data 12 noiembrie 2017 18:06:29
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<fstream>
#include<algorithm>
#define DIM 16005
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int N, M;
vector<int> A[6*DIM];
long long sol;
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 nod, int st, int dr ){
    if( st == dr ){
        A[nod].push_back( P[st].y );
    }else{
        int mid = ( ( st + dr ) >> 1 );
        int Nst = (nod << 1);
        int Ndr = ( (nod << 1) | 1 );
        build( Nst, st, mid );
        build( Ndr, mid + 1, dr );
        for( int i = 0, j = 0; i < A[Nst].size() || j < A[Ndr].size(); ){
            if( i == A[Nst].size() ){
                A[nod].push_back( A[Ndr][j++] );
                continue;
            }
            if( j == A[Ndr].size() ){
                A[nod].push_back( A[Nst][i++] );
                continue;
            }
            if( A[Nst][i] <= A[Ndr][j] )
                A[nod].push_back( A[Nst][i++] );
            else
                A[nod].push_back( A[Ndr][j++] );
        }
    }
}
void query( int nod, int st, int dr, int X1, int X2, int Y1, int Y2 ){
    int Nst = (nod << 1);
    int Ndr = ( (nod << 1) | 1 );
    if( st > dr )
        return;
    if( X1 <= P[st].x && P[dr].x <= X2 ){
        int p, u, m, p1, p2;
        p = 0; u = A[nod].size() - 1;
        while( p <= u ){
            m = ( p + u ) >> 1;
            if( A[nod][m] < Y1 )
                p = m + 1;
            else
                u = m - 1;
        }
        p1 = p;
        p = 0; u = A[nod].size() - 1;
        while( p <= u ){
            m = ( p + u ) >> 1;
            if( A[nod][m] <= Y2 )
                p = m + 1;
            else
                u = m - 1;
        }
        p2 = u;
        if( p1 > p2 )
            return;
        sol += p2 - p1 + 1;
    }else{
        int mid = ( ( st + dr ) >> 1 );
        if( X1 <= P[mid].x )
            query( Nst, st, mid, X1, X2, Y1, Y2  );
        if( X2 >= P[mid + 1].x )
            query( Ndr, mid + 1, dr, X1, X2, Y1, Y2  );
    }
    return;
}
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ )
        fin >> P[i].x >> P[i].y;
    sort( P + 1, P + N + 1, cmp );
    build( 1, 1, N );
    fin >> M;
    for( int i = 1; i <= M; i++ ){
        int X1, X2, Y1, Y2;
        fin >> X1 >> Y1 >> X2 >> Y2;
        sol = 0;
        query( 1, 1, N, X1, X2, Y1, Y2 );
        fout << sol << "\n";
    }
    return 0;
}