Pagini recente » Cod sursa (job #2708134) | Cod sursa (job #123257) | Cod sursa (job #2191967) | Cod sursa (job #2864641) | Cod sursa (job #3163834)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct drept {
int x1;
int x2;
int y1;
int y2;
};
drept q;
pair<int, int> p[16001];
vector<int> AINT[4 * 16001];
//int s[250001];
int n, m, k;
void build(int nod, int st, int dr) {
for (int i = st; i <= dr; i++) {
AINT[nod].push_back(p[i].second);
}
sort(AINT[nod].begin(), AINT[nod].end());
if (st >= dr)
return;
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
}
int positionOfEnd(int x, int nod) {
int position = 0;
int st = 0;
int dr = AINT[nod].size() - 1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (AINT[nod][mid] <= x) {
position = mid;
st = mid + 1;
}
else {
position = mid - 1;
dr = mid - 1;
}
}
return position;
}
int positionOfStart(int x, int nod) {
int position = 0;
int st = 0;
int dr = AINT[nod].size() - 1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (x <= AINT[nod][mid]) {
position = mid;
dr = mid - 1;
}
else {
position = mid + 1;
st = mid + 1;
}
}
return position;
}
int elementsInInterval(int start, int end, int nod) {
return positionOfEnd(end, nod) - positionOfStart(start, nod) + 1;
}
int query(int nod, int st, int dr, drept &d) {
if (d.x1 <= p[st].first && p[dr].first <= d.x2) {
return elementsInInterval(d.y1, d.y2, nod);
}
else {
int mid = (st + dr) / 2;
int elements = 0;
if (d.x1 <= p[mid].first)
elements += query(2 * nod, st, mid, d);
if (p[mid].first < d.x2)
elements += query(2 * nod + 1, mid + 1, dr, d);
return elements;
}
}
/*
int normalizedValue(int x) {
int st = 1;
int dr = k;
while (st <= dr) {
int mid = (st + dr) / 2;
if (s[mid] == x)
return mid;
if (x < s[mid])
dr = mid - 1;
else
st = mid + 1;
}
}
*/
int main()
{
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> p[i].first >> p[i].second;
// s[++k] = p[i].first;
}
/*
fin >> m;
for (int i = 1; i <= m; i++) {
fin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2;
s[++k] = q[i].x1;
s[++k] = q[i].x2;
}
*/
/*
sort(s + 1, s + k + 1);
int last = 0;
s[++last] = s[1];
for (int i = 2; i <= k; i++) {
if (s[i] != s[i - 1]) {
s[++last] = s[i];
}
}
k = last;
for (int i = 1; i <= n; i++) {
p[i].first = normalizedValue(p[i].first);
}
for (int i = 1; i <= m; i++) {
q[i].x1 = normalizedValue(q[i].x1);
q[i].x2 = normalizedValue(q[i].x2);
}
*/
sort(p + 1, p + n + 1);
build(1, 1, n);
fin >> m;
for (int i = 1; i <= m; i++) {
fin >> q.x1 >> q.y1 >> q.x2 >> q.y2;
fout << query(1, 1, n, q) << "\n";
}
}