Pagini recente » Cod sursa (job #64576) | Cod sursa (job #189503) | Cod sursa (job #246542) | Cod sursa (job #33928) | Cod sursa (job #3162125)
#include <bits/stdc++.h>
using namespace std;
string file = "zoo";
ifstream fin(file + ".in");
ofstream fout(file + ".out");
int n, m;
pair <int, int> v[100001];
vector <int> t[100001];
void build(int i = 1, int l = 1, int r = n) {
if (l == r) {
t[i].resize(1);
t[i][0] = v[l].second;
return;
}
int m = (l + r) >> 1;
int aux = (i << 1);
build(aux, l, m);
build(aux + 1, m + 1, r);
vector <int>::iterator it1, it2;
it1 = t[aux].begin();
it2 = t[aux + 1].begin();
while (it1 != t[aux].end() && it2 != t[aux + 1].end())
if (*it1 < *it2)
t[i].push_back(*it1), it1++;
else
t[i].push_back(*it2), it2++;
while (it1 != t[aux].end())
t[i].push_back(*it1), it1++;
while (it2 != t[aux + 1].end())
t[i].push_back(*it2), it2++;
}
int get(int x1, int y1, int x2, int y2, int i = 1, int l = 1, int r = n) {
if (x2 < v[l].first || v[r].first < x1)
return 0;
if (x1 <= v[l].first && v[r].first <= x2) {
int Left = 0, Right = t[i].size() - 1, pos1 = -1, pos2 = -1;
while (Left <= Right) {
int mid = (Left + Right) >> 1;
if (t[i][mid] >= y1) {
pos1 = mid;
Right = mid - 1;
}
else
Left = mid + 1;
}
if (pos1 == -1)
return 0;
Left = pos1;
Right = t[i].size() - 1;
while (Left <= Right) {
int mid = (Left + Right) >> 1;
if (t[i][mid] <= y2) {
pos2 = mid;
Left = mid + 1;
}
else
Right = mid - 1;
}
return pos2 - pos1 + 1;
}
int m = (l + r) >> 1;
return get(x1, y1, x2, y2, (i << 1), l, m) + get(x1, y1, x2, y2, (i << 1) + 1, m + 1, r);
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1);
build();
fin >> m;
for (int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
fout << get(x1, y1, x2, y2) << '\n';
}
return 0;
}