Cod sursa(job #1202230)

Utilizator andreiiiiPopa Andrei andreiiii Data 27 iunie 2014 13:02:16
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int Nmax = 16005, INF = 2000000005;

pair<int, int> Points[Nmax];

int N;

vector<int> Aint[4 * Nmax];

void Build(const int node, const int left, const int right)
{
    Aint[node] = vector<int>(right - left + 2);
    Aint[node][0] = -INF;

    if (left == right)
    {
        Aint[node][1] = Points[left].second;
        return;
    }

    const int mid = (left + right) / 2;

    Build(2 * node, left, mid);
    Build(2 * node + 1, mid + 1, right);

    merge(Aint[2 * node].begin() + 1, Aint[2 * node].end(), Aint[2 * node + 1].begin() + 1, Aint[2 * node + 1].end(), Aint[node].begin() + 1);
}

int Query(const int node, const int left, const int right, const int x1, const int y1, const int x2, const int y2)
{
    if (x1 <= Points[left].first && Points[right].first <= x2)
        return (upper_bound(Aint[node].begin(), Aint[node].end(), y2) - lower_bound(Aint[node].begin(), Aint[node].end(), y1));

    if (left == right) return 0;

    const int mid = (left + right) / 2;
    int ret = 0;

    if (x1 <= Points[mid].first) ret += Query(2 * node, left, mid, x1, y1, x2, y2);
    if (x2 > Points[mid + 1].first) ret += Query(2 * node + 1, mid + 1, right, x1, y1, x2, y2);

    return ret;
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d%d", &Points[i].first, &Points[i].second);

    sort(Points + 1, Points + N + 1);
    Build(1, 1, N);

    int Q;
    scanf("%d", &Q);

    while (Q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        printf("%d\n", Query(1, 1, N, x1, y1, x2, y2));
    }

}