Pagini recente » Cod sursa (job #398496) | Cod sursa (job #2956462) | Cod sursa (job #2671360) | Cod sursa (job #2916357)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct Point {
int x, y;
};
vector<Point> Points, Queries;
vector<int> values;
vector<int> answers;
int normalize(int value) {
return distance(values.begin(), lower_bound(values.begin(), values.end(), value)) + 1;
}
template <typename T>
struct implicitFenwickTree {
int N;
vector<vector<T>> tree;
implicitFenwickTree () {
}
implicitFenwickTree(int size) {
N = size;
tree = vector<vector<T>> (size + 1);
}
implicitFenwickTree& operator = (const implicitFenwickTree &DS) {
N = DS.N;
tree = DS.tree;
return *this;
}
int lsb(int i) {
return i & (-i);
}
void insert(int x, int y) {
for(int i = x; i <= N; i += lsb(i)) {
tree[i].push_back(y);
}
}
void sortAll() {
for(int i = 1; i <= N; i++) {
sort(tree[i].begin(), tree[i].end());
}
}
int query(int x, int y) {
int ret = 0;
for(int i = x; i > 0; i -= lsb(i)) {
ret += distance(tree[i].begin(), lower_bound(tree[i].begin(), tree[i].end(), y + 1));
}
return ret;
}
};
int N, M;
implicitFenwickTree<int> DS;
int main() {
fin >> N;
Points = vector<Point> (N);
for(auto &p: Points) {
fin >> p.x >> p.y;
}
fin >> M;
for(int i = 0; i < M; i++) {
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
Queries.push_back({x2, y2});
Queries.push_back({x1 - 1, y2});
Queries.push_back({x2, y1 - 1});
Queries.push_back({x1 - 1, y1 - 1});
}
for(const auto &p: Points) {
values.push_back(p.x);
}
for(const auto &q: Queries) {
values.push_back(q.x);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
for(auto &p: Points) {
p.x = normalize(p.x);
}
for(auto &q: Queries) {
q.x = normalize(q.x);
}
DS = implicitFenwickTree<int> (values.size());
for(const auto &p: Points) {
DS.insert(p.x, p.y);
}
DS.sortAll();
for(int i = 0; i < (int) Queries.size(); i += 4) {
int a = DS.query(Queries[i].x, Queries[i].y);
int b = DS.query(Queries[i + 1].x, Queries[i + 1].y);
int c = DS.query(Queries[i + 2].x, Queries[i + 2].y);
int d = DS.query(Queries[i + 3].x, Queries[i + 3].y);
fout << a - b - c + d << '\n';
}
return 0;
}