Pagini recente » Cod sursa (job #401471) | Cod sursa (job #283234) | Cod sursa (job #2908608)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int LEFT = 1;
const int POINT = 2;
const int RIGHT = 3;
struct Event {
int TYPE;
int x, y;
int y1, y2;
int index;
};
struct Point {
int x, y;
};
struct Query {
int x1, y1;
int x2, y2;
int index;
};
vector<Event> Events;
vector<Point> Points;
vector<Query> 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 Fenwick {
int N;
vector<T> tree;
Fenwick () {
}
Fenwick(int size) {
N = size;
tree = vector<T> (size);
}
Fenwick& operator = (const Fenwick &_) {
N = _.N;
tree = _.tree;
return *this;
}
int lsb(int i) {
return i & (-i);
}
void update(int position, int value) {
for(int i = position; i <= N; i += lsb(i)) {
tree[i] += value;
}
}
int query(int position) {
int ret = 0;
for(int i = position; i > 0; i -= lsb(i)) {
ret += tree[i];
}
return ret;
}
int query(int left, int right) {
return query(right) - query(left - 1);
}
};
int N, M;
Fenwick<int> DS;
int main() {
fin >> N;
Points = vector<Point> (N);
for(auto &p: Points) {
fin >> p.x >> p.y;
}
fin >> M;
Queries = vector<Query> (M);
int index = 0;
for(auto &q: Queries) {
fin >> q.x1 >> q.y1 >> q.x2 >> q.y2;
q.index = index++;
}
for(auto p: Points) {
values.push_back(p.y);
}
for(auto q: Queries) {
values.push_back(q.y1);
values.push_back(q.y2);
}
sort(values.begin(), values.end());
for(auto &p: Points) {
p.y = normalize(p.y);
}
for(auto &q: Queries) {
q.y1 = normalize(q.y1);
q.y2 = normalize(q.y2);
}
for(auto p: Points) {
Events.push_back({POINT, p.x, p.y, 0, 0, 0});
}
for(auto q: Queries) {
Events.push_back({LEFT, q.x1, 0, q.y1, q.y2, q.index});
Events.push_back({RIGHT, q.x2, 0, q.y1, q.y2, q.index});
}
sort(Events.begin(), Events.end(), [] (const Event &a, const Event &b) {
if(a.x == b.x) {
return a.TYPE < b.TYPE;
}
return a.x < b.x;
});
answers = vector<int> (M);
DS = Fenwick<int> (values.back());
for(auto e: Events) {
if(e.TYPE == POINT) {
DS.update(e.y, 1);
} else if(e.TYPE == LEFT) {
answers[e.index] = -DS.query(e.y1, e.y2);
} else {
answers[e.index] += DS.query(e.y1, e.y2);
}
}
for(auto a: answers) {
fout << a << '\n';
}
return 0;
}