Cod sursa(job #1536513)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 noiembrie 2015 12:18:10
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define DIM 16384
#define INF 2147483647
#define x first
#define y second
using namespace std;

int N, M, X1, Y1, X2, Y2;
vector <int> ArbInt[DIM*4];
pair <int, int> Points[DIM];

void build (int pos, int left, int right) {
    if (left == right)
        ArbInt[pos].push_back(left);
    else {
        int mid = left + (right - left) / 2, i = 0, j = 0;

        build (pos * 2 + 0,  left  ,  mid );
        build (pos * 2 + 1, mid + 1, right);

        while (i < ArbInt[pos*2].size() || j < ArbInt[pos*2+1].size()) {
            int val1 = (i == ArbInt[pos*2+0].size()) ? 0 : ArbInt[pos*2+0][i];
            int val2 = (j == ArbInt[pos*2+1].size()) ? 0 : ArbInt[pos*2+1][j];

            if (Points[val1].y <= Points[val2].y) {
                ArbInt[pos].push_back(val1);
                i ++;
            } else {
                ArbInt[pos].push_back(val2);
                j ++;
            }
        }
    }
    return;
}

int query (int pos, int left, int right, int X1, int Y1, int X2, int Y2) {
    if (X1 <= Points[left].x && Points[right].x <= X2) {
        int start, finish, mid, pos1, pos2;

        start = 0, finish = ArbInt[pos].size() - 1;
        while (start <= finish) {
            mid = start + (finish - start) / 2;

            if (Points[ArbInt[pos][mid]].y >= Y1)
                finish = mid - 1;
            else
                start  = mid + 1;
        }
        pos1 = start;

        start = 0; finish = ArbInt[pos].size() - 1;
        while (start <= finish) {
            mid = start + (finish - start) / 2;

            if (Points[ArbInt[pos][mid]].y <= Y2)
                start  = mid + 1;
            else
                finish = mid - 1;
        }
        pos2 = finish;

        return pos2 - pos1 + 1;
    } else {
        int mid = left + (right - left) / 2, nrPoints = 0;

        if (left == right)
            return 0;

        if (Points[mid+0].x >= X1)
            nrPoints += query (pos * 2 + 0,  left  ,  mid , X1, Y1, X2, Y2);

        if (Points[mid+1].x <= X2)
            nrPoints += query (pos * 2 + 1, mid + 1, right, X1, Y1, X2, Y2);

        return nrPoints;
    }
    return -1;
}

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].x, &Points[i].y);

    sort(Points + 1, Points + N + 1);
    Points[0].y = INF; build (1, 1, N);

    scanf ("%d", &M);
    for (int i = 1; i <= M; i ++) {
        scanf ("%d %d", &X1, &Y1);
        scanf ("%d %d", &X2, &Y2);
        printf ("%d\n", query (1, 1, N, X1, Y1, X2, Y2));
    }

    return 0;
}