Cod sursa(job #1083230)

Utilizator deneoAdrian Craciun deneo Data 15 ianuarie 2014 19:11:47
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

std::ifstream fin("zoo.in");
std::ofstream fout("zoo.out");

const int MAXN = 16200;

#define For(i, st, dr) for (int (i) = (st); (i) <= (dr); ++(i))

int n, m;
std::vector<int> aint[3 * MAXN], bridge[3 * MAXN][2];
std::pair<int, int> points[MAXN];
std::vector<int> a;

inline void build_my_vector(int nod, int st, int dr) {
    register int stp, drp, n, m;

    stp = drp = 0;
    n = aint[st].size();
    m = aint[dr].size();

    aint[nod].resize(n + m);
    bridge[nod][0].resize(n + m);
    bridge[nod][1].resize(n + m);

    register int pas = 0;

    while (stp < n || drp < m) {
        // stanga
        bridge[nod][0][pas] = stp;
        bridge[nod][1][pas] = drp;
        if (stp != n && (drp == m || aint[dr][drp] > aint[st][stp])) {
            aint[nod][pas] = aint[st][stp];
            ++stp;
        }
        else {
            aint[nod][pas] = aint[dr][drp];
            ++drp;
        }
        ++pas;
    }
}

void build(int nod, int st, int dr) {
    if (st == dr) {
        aint[nod].push_back(points[st].second);
        return;
    }
    int mid = (st + dr) >> 1;
    int stanga = nod << 1;
    int dreapta = (nod << 1) + 1;

    build (stanga, st, mid);
    build (dreapta, mid + 1, dr);

    build_my_vector(nod, stanga, dreapta);

}

void query_aint(int nod, int st, int dr, int &l, int &r, int pozl, int pozr, int &rez) {
    if (pozl > pozr) return;

    if (l <= st && dr <= r) {
        rez += pozr - pozl + 1;
        return;
    }

    int mid = (st + dr) >> 1;

    if (l <= mid) {
        int stanga = nod << 1;
        register int lefty = bridge[nod][0][pozr];
        if (lefty >= aint[stanga].size() || aint[stanga][lefty] > aint[nod][pozr])
            --lefty;
        query_aint(stanga, st, mid, l, r, bridge[nod][0][pozl], lefty, rez);
    }
    if (r > mid) {
        int dreapta = (nod << 1) + 1;
        register int righty = bridge[nod][1][pozr];
        if (righty >= aint[dreapta].size() || aint[dreapta][righty] > aint[nod][pozr])
            --righty;
        query_aint(dreapta, mid + 1, dr, l, r, bridge[nod][1][pozl], righty, rez);
    }
}


inline int query(int x1, int y1, int x2, int y2) {
    int px1 = lower_bound(a.begin(), a.end(), x1) - a.begin() + 1;
    int px2 = upper_bound(a.begin(), a.end(), x2) - a.begin();

    int py1 = lower_bound(aint[1].begin(), aint[1].end(), y1) - aint[1].begin();
    int py2 = upper_bound(aint[1].begin(), aint[1].end(), y2) - aint[1].begin() - 1;

    if (px1 > px2 || py1 > py2) return 0;

    int rez = 0;
    query_aint(1, 1, n, px1, px2, py1, py2, rez);

    return rez;
}

int main() {
    fin >> n;

    For (i, 1, n) {
        fin >> points[i].first >> points[i].second;
        a.push_back(points[i].first);
    }

    sort(points + 1, points + n + 1);
    sort(a.begin(), a.end());

    build(1, 1, n);

    fin >> m;

    For(i, 1, m) {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        fout << query(x1, y1, x2, y2) << "\n";
    }

    return 0;
}