Pagini recente » Cod sursa (job #3237637) | Cod sursa (job #1527038) | Cod sursa (job #2762183)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int MAXN = 16000;
const int MAXM = 1e5;
struct point {
int x, y;
void read() {
fin >> x >> y;
}
bool operator < (const point &A) const {
if (x != A.x)
return x < A.x;
return y < A.y;
}
} v[1 + MAXN];
struct query {
int x1, y1, x2, y2, index;
void read() {
fin >> x1 >> y1 >> x2 >> y2;
}
bool operator < (const query &A) const {
if (x1 != A.x1)
return x1 < A.x1;
if (x2 != A.x2)
return x2 < A.x2;
if (y1 != A.y1)
return y1 < A.y1;
return y2 < A.y2;
}
} q[1 + MAXM];
int N, aib[1 + MAXN + 2 * MAXM], sol[1 + MAXM];
void update(int x, int t) {
for (int i = x; i <= N; i += i & -i)
aib[i] += t;
}
int query(int l, int r) {
int ans = 0;
for (int i = r; i > 0; i -= i & -i)
ans += aib[i];
for (int i = l - 1; i > 0; i -= i & -i)
ans -= aib[i];
return ans;
}
int main() {
int n;
fin >> n;
vector<int> Y;
for (int i = 1; i <= n; ++i) {
v[i].read();
Y.emplace_back(v[i].y);
}
sort(v + 1, v + n + 1);
int m;
fin >> m;
for (int i = 1; i <= m; ++i) {
q[i].read();
q[i].index = i;
Y.emplace_back(q[i].y1);
Y.emplace_back(q[i].y2);
}
sort(q + 1, q + m + 1);
sort(Y.begin(), Y.end());
unordered_map<int,int> val;
val[Y.front()] = ++N;
for (size_t i = 1; i < Y.size(); ++i)
if (Y[i] != Y[i - 1])
val[Y[i]] = ++N;
for (int i = 1; i <= n; ++i)
v[i].y = val[v[i].y];
for (int i = 1; i <= m; ++i) {
q[i].y1 = val[q[i].y1];
q[i].y2 = val[q[i].y2];
}
val.clear();
int p1 = 1, p2 = 1;
for (int i = 1; i <= m; ++i) {
while (p2 <= n && v[p2].x <= q[i].x2) {
update(v[p2].y, 1);
++p2;
}
while (p1 <= n && v[p1].x < q[i].x1) {
update(v[p1].y, -1);
++p1;
}
sol[q[i].index] = query(q[i].y1, q[i].y2);
}
for (int i = 1; i <= m; ++i)
fout << sol[i] << '\n';
fin.close();
fout.close();
return 0;
}