Cod sursa(job #741897)

Utilizator deneoAdrian Craciun deneo Data 27 aprilie 2012 12:50:13
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

#define ns nod * 2
#define nd nod * 2 + 1
#define MAXN 16100
#define x first
#define y second

vector<int> arb[3 * MAXN];
pair<int, int> v[MAXN];
int n, m;

void build (int nod, int st, int dr) {
    if (st == dr) {
        arb[nod].push_back(v[st].y);
        return;
    }
    build(ns, st, (st + dr) / 2);
    build(nd, (st + dr) / 2 + 1, dr);
    arb[nod].resize(arb[ns].size() + arb[nd].size());
    merge(arb[ns].begin(), arb[ns].end(), arb[nd].begin(), arb[nd].end(), arb[nod].begin());
}

int query (int nod, int st, int dr, int x1, int x2, int y1, int y2) {
    int rez = 0, mid = (st + dr) / 2;
    if (x1 <= v[st].x && v[dr].x <= x2) {
        return lower_bound(arb[nod].begin(), arb[nod].end(), y2 + 1) - lower_bound(arb[nod].begin(), arb[nod].end(), y1);
    }
    if (st == dr) return 0;
    if (x1 <= v[mid].x)
        rez += query (ns, st, mid, x1, x2, y1, y2);
    if (x2 > v[mid].x)
        rez += query (nd, mid + 1, dr, x1, x2, y1, y2);
    return rez;
}

int main() {
    int i, x1, x2, y1, y2, minX, maxX;
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
    sort (v + 1, v + n + 1);
    build (1, 1, n);
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> x1 >> y1 >> x2 >> y2;
        fout << query(1, 1, n, max (x1, v[0].x), min(x2, v[n].x), y1, y2) << "\n";
    }
    fout.close();
    return 0;
}