Cod sursa(job #1827772)

Utilizator mirupetPetcan Miruna mirupet Data 12 decembrie 2016 12:24:45
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
FILE *fin = freopen("zoo.in", "r", stdin);
FILE *fout = freopen("zoo.out", "w", stdout);

int N, M, start, finish, X1, X2, Y1, Y2, sol;
pair < int, int > v[16002];
vector < int > arb[16385 * 8], w;

void Build(int node, int left, int right)
{
    if (left == right)
    {
        arb[node].push_back(v[left].second);
        return;
    }

    int div = (left + right) >> 1;
    Build(2 * node, left, div);
    Build(2 * node + 1, div + 1, right);

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

void Query(int node, int left, int right)
{
    int a, b;
    if (start <= left && right <= finish)
    {
        a = lower_bound(arb[node].begin(), arb[node].end(), Y1) - arb[node].begin();
        b = upper_bound(arb[node].begin(), arb[node]. end(), Y2) - arb[node].begin();
        sol += b - a;
        return;
    }

    if (left != right)
    {
        int div = (left + right) >> 1;
        if (start <= div)    Query(2 * node, left, div);
        if (div < finish)    Query(2 * node + 1, div + 1, right);
    }
}

int main()
    {
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
        {
            scanf("%d%d", &v[i].first, &v[i].second);
            w.push_back(v[i].first);
        }
        sort(w.begin(), w.end());
        sort(v + 1, v + N + 1);
        Build(1, 1, N);

        scanf("%d", &M);
        while (M--)
        {
            scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
            start = lower_bound(w.begin(), w.end(), X1) - w.begin() + 1;
            finish = upper_bound(w.begin(), w.end(), X2) - w.begin();
            sol = 0;
            Query(1, 1, N);
            printf("%d\n", sol);
        }
    }