Cod sursa(job #1404919)

Utilizator vladrochianVlad Rochian vladrochian Data 28 martie 2015 17:31:55
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> Pair;
typedef vector<Pair>::iterator Iterator;
const int kMaxArb = 32775;
const int kInf = 2000000005;

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

vector<Pair> p;
vector<int> aint[kMaxArb];

int N, M;

void Build(int node, Iterator begin, Iterator end) {
	if (end - begin == 1) {
		aint[node].assign(1, begin->second);
		return;
	}
	Iterator mid = begin + ((end - begin) >> 1);
	int ls = node << 1, rs = ls + 1;
	Build(ls, begin, mid);
	Build(rs, mid, end);
	aint[node].resize(end - begin);
	merge(aint[ls].begin(), aint[ls].end(), aint[rs].begin(), aint[rs].end(), aint[node].begin());
}

int Query(int node, Iterator begin, Iterator end, Iterator l, Iterator r, int y1, int y2) {
	if (begin >= end || end <= l || r <= begin)
		return 0;
	if (l <= begin && end <= r)
		return upper_bound(aint[node].begin(), aint[node].end(), y2) -
		       lower_bound(aint[node].begin(), aint[node].end(), y1);
	Iterator mid = begin + ((end - begin) >> 1);
	int ls = node << 1, rs = ls + 1;
	return Query(ls, begin, mid, l, r, y1, y2) + Query(rs, mid, end, l, r, y1, y2);
}

int main() {
	fin >> N;
	p.resize(N);
	for (auto &it : p)
		fin >> it.first >> it.second;
	sort(p.begin(), p.end());
	Build(1, p.begin(), p.end());
	fin >> M;
	while (M--) {
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;
		fout << Query(1, p.begin(), p.end(),
		              lower_bound(p.begin(), p.end(), Pair(x1, -kInf)),
		              upper_bound(p.begin(), p.end(), Pair(x2, kInf)),
		              y1, y2) << "\n";
	}
	return 0;
}