Cod sursa(job #1157537)

Utilizator cbanu96Banu Cristian cbanu96 Data 28 martie 2014 16:26:47
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define FILEIN "zoo.in"
#define FILEOUT "zoo.out"
#define NMAX 65536

vector<int> AINT[NMAX];
pair<int, int> Pct[NMAX];

int N, M;
int sol;
int xA, yA, xB, yB;

void initTree(int nod, int left, int right, const int& pos) {
    AINT[nod].push_back(0);

    if (left == right)
        return;

    int m = (left+right)/2;
    if (pos <= m)
        initTree(2*nod, left, m, pos);
    else
        initTree(2*nod+1, m+1, right, pos);
}

void updateTree(int nod, int left, int right, const int& pos) {
    if (left == right) {
        AINT[nod][0] = Pct[pos].second;
        return;
    }

    int m = (left + right)/2;
    if (pos <= m)
        updateTree(2*nod, left, m, pos);
    else
        updateTree(2*nod+1, m+1, right, pos);

    if (pos == right) {
        merge(AINT[2*nod].begin(), AINT[2*nod].end(), AINT[2*nod+1].begin(), AINT[2*nod+1].end(),
              AINT[nod].begin());
    }
}

void queryTree(int nod, int left, int right) {
    if (xA <= Pct[left].first && Pct[right].first <= xB) {
        sol += upper_bound(AINT[nod].begin(), AINT[nod].end(), yB) - lower_bound(AINT[nod].begin(), AINT[nod].end(), yA);
        return;
    }

    if (left == right)
        return;

    int m = (left+right)/2;

    if (xA <= Pct[m].first)   queryTree(2*nod, left, m);
    if (Pct[m+1].first <= xB) queryTree(2*nod+1, m+1, right);
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT ,"w", stdout);
    scanf("%d", &N);

    for ( int i = 1, x, y; i <= N; i++ ) {
        scanf("%d %d", &x, &y);
        Pct[i] = make_pair(x, y);
    }

    for ( int i = 1; i <= N; i++ ) {
        initTree(1, 1, N, i);
    }

    sort(Pct+1, Pct+N+1);

    for ( int i = 1; i <= N; i++ ) {
        updateTree(1, 1, N, i);
    }

    for ( scanf("%d", &M); M; M--)  {
        scanf("%d %d %d %d", &xA, &yA, &xB, &yB);
        sol = 0;
        queryTree(1, 1, N);
        printf("%d\n", sol);
    }

    return 0;
}