Pagini recente » Cod sursa (job #2831559) | Cod sursa (job #3179339) | Cod sursa (job #523847) | Cod sursa (job #862602) | Cod sursa (job #2579363)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
class FenTree {
private:
int n;
vector<int> bit;
public:
FenTree(int n) :
n(n), bit(n + 1) { }
void update(int pos) {
for (int i = pos; i <= n; i += i & -i)
bit[i]++;
}
int query(int pos) {
int sum = 0;
for (int i = pos; i >= 1; i -= i & -i)
sum += bit[i];
return sum;
}
int query(int left, int right) {
return query(right) - query(left - 1);
}
};
struct Tripl {
int x, y, z;
Tripl(int x, int y, int z) :
x(x), y(y), z(z) { }
inline bool operator<(const Tripl& t) const {
return x < t.x;
}
};
struct Entry {
int t, x, y;
Entry(int t, int x, int y) :
t(t), x(x), y(y) { }
inline int& operator[](int ind) {
return ind ? y : x;
}
inline bool operator<(const Entry& e) const {
return x < e.x || (x == e.x && (y < e.y || (y == e.y && t < e.t)));
}
};
int main() {
vector<Entry> evn;
vector<Tripl> val;
int n; fin >> n;
evn.reserve(n);
val.reserve(2 * n);
for (int i = 0; i < n; i++) {
int x, y; fin >> x >> y;
evn.emplace_back(0, x, y);
val.emplace_back(x, evn.size() - 1, 0);
val.emplace_back(y, evn.size() - 1, 1);
}
int q; fin >> q;
evn.reserve(n + q);
val.reserve(2 * n + 4 * q);
for (int i = 1; i <= q; i++) {
int x1, y1, x2, y2; fin >> x1 >> y1 >> x2 >> y2;
evn.emplace_back(-i, x1, y1);
val.emplace_back(x1, evn.size() - 1, 0);
val.emplace_back(y1, evn.size() - 1, 1);
evn.emplace_back(+i, x2, y2);
val.emplace_back(x2, evn.size() - 1, 0);
val.emplace_back(y2, evn.size() - 1, 1);
}
sort(val.begin(), val.end());
int cnt = 0;
vector<pair<int, int>> qry(q + 1);
for (int i = 0; i < (int) val.size(); i++) {
if (!i || val[i - 1].x != val[i].x)
cnt++;
evn[val[i].y][val[i].z] = cnt;
if (val[i].z == 1) {
if (evn[val[i].y].t < 0)
qry[-evn[val[i].y].t].first = cnt;
else
qry[+evn[val[i].y].t].second = cnt;
}
}
sort(evn.begin(), evn.end());
FenTree tree(cnt);
vector<int> ans(q + 1);
for (auto& e : evn)
if (e.t < 0)
ans[-e.t] -= tree.query(qry[-e.t].first, qry[-e.t].second);
else if (e.t > 0)
ans[+e.t] += tree.query(qry[+e.t].first, qry[+e.t].second);
else
tree.update(e.y);
for (int i = 1; i <= q; i++)
fout << ans[i] << '\n';
fout.close();
return 0;
}