Cod sursa(job #1211410)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 iulie 2014 15:58:13
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 16e3 + 2;

#define Point pair<int,int>
#define x first
#define y second

int N, M;
Point P[Nmax];

vector <int> A[4 * Nmax];

void build( int nod, int st, int dr )
{
    A[nod] = vector <int>( dr - st + 1 );

    if ( st == dr )
    {
        A[nod][0] = P[st].y;
    }
    else
    {
        int m = ( st + dr ) / 2;

        build( 2 * nod, st, m );
        build( 2 * nod + 1, m + 1, dr );

        merge(A[2 * nod].begin() , A[2 * nod].end(), A[2 * nod + 1].begin() , A[2 * nod + 1].end(), A[nod].begin() );
    }
}

int query( int nod, int st, int dr, int x1, int y1, int x2, int y2 )
{
    if ( x1 <= P[st].x && P[dr].x <= x2 )
    {
        int q1 = upper_bound( A[nod].begin(), A[nod].end(), y2 ) - A[nod].begin();
        int q2 = lower_bound( A[nod].begin(), A[nod].end(), y1 ) - A[nod].begin();
        return q2 - q1;
    }
    else
    {
        int m = ( st + dr ) / 2;
        int sol = 0;

        if ( x1 <= P[m].x )
            sol += query( 2 * nod, st, m, x1, y1, x2, y2 );

        if ( P[m].x < x2 )
            sol += query( 2 * nod + 1, m + 1, dr, x1, y1, x2, y2 );

        return sol;
    }
}

int main()
{
    ifstream in("zoo.in");
    ofstream out("zoo.out");

    in.sync_with_stdio( false );

    in >> N;

    for ( int i = 0; i < N; ++i )
        in >> P[i].x >> P[i].y;

    sort( P, P + N );
    build( 1, 0, N - 1 );

    in >> M;

    for ( int i = 0; i < M; ++i )
    {
        int x1, x2, y1, y2;

        in >> x1 >> y1 >> x2 >> y2;
        out << query( 1, 0, N - 1, x1, y1, x2, y2 ) << "\n";
    }

    return 0;
}