Cod sursa(job #1827760)

Utilizator mirupetPetcan Miruna mirupet Data 12 decembrie 2016 11:57:59
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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;
struct point{int x, y;};
point v[16002];
vector < int > arb[16385 * 4], w;

bool comp(point a, point b)
{
    if (a.x == b.x) return (a.y <= b.y);
                    return (a.x < b.x);
}

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

    int div = (left + right) / 2;
    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;
    }

    int div = (left + right) / 2;
    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].x, &v[i].y);
            w.push_back(v[i].x);
        }
        sort(w.begin(), w.end());
        sort(v + 1, v + N + 1, comp);
        Build(1, 1, N);

        /*for (int i = 1; i <= 8; i++, printf("\n"))
            for (int j = 0; j < arb[i].size(); j++)
                printf("%d ", arb[i][j]);*/
        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);
        }
    }