Pagini recente » Cod sursa (job #2065451) | Cod sursa (job #3246198) | Cod sursa (job #460321) | Cod sursa (job #730739) | Cod sursa (job #3166880)
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const long long INF = 1000000000000000000;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(A) A.begin(), A.end()
using ll = long long;
ifstream fin(".in");
ofstream fout(".out");
#define variableName(var) #var
#define __debug(var) cout << #var << " = " << var << '\n'
inline int rint(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
struct point {
int x, y;
};
int n, m;
vector<point> points;
vector<pair<point, point>> querys;
vector<int> ans;
struct fenwick {
vector<int> t;
void build(int size) {
t.resize(size + 1);
}
void add(int i, int x) {
for (; i < t.size(); i += i & -i) {
t[i] += x;
}
}
int get(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) {
sum += t[i];
}
return sum;
}
int get(int i, int j) {
return get(j) - get(i - 1);
}
} tree;
void normalizeInput() {
map<int, int> normx;
map<int, int> normy;
for (auto& p : points) {
normx[p.x] = normy[p.y] = 0;
}
for (auto& q : querys) {
normx[q.first.x] = normx[q.second.x] = normy[q.first.y] = normy[q.second.y] = 0;
}
for (auto& it : normx) {
static int k = 0;
it.second = ++k;
}
for (auto& it : normy) {
static int k = 0;
it.second = ++k;
}
for (auto& p : points) {
p.x = normx[p.x];
p.y = normy[p.y];
}
for (auto& q : querys) {
q.first.x = normx[q.first.x];
q.first.y = normy[q.first.y];
q.second.x = normx[q.second.x];
q.second.y = normy[q.second.y];
}
tree.build(normy.rbegin()->second + 5);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
points.resize(n + 1);
ans.resize(n + 1);
for (int i = 1; i <= n; ++i) {
fin >> points[i].x >> points[i].y;
}
fin >> m;
querys.resize(m + 1);
for (int i = 1; i <= m; ++i) {
fin >> querys[i].first.x >> querys[i].first.y >> querys[i].second.x >> querys[i].second.y;
}
normalizeInput();
struct operation {
int x;
int i;
int t; // 0 - enter block, 1 - add point, 2 - exit block
bool operator<(const operation& other) {
return x != other.x ? x < other.x : t < other.t;
}
};
vector<operation> operations;
for (int i = 1; i <= m; ++i) {
operations.push_back({ querys[i].first.x, i, 0 });
operations.push_back({ querys[i].second.x, i, 2 });
}
for (int i = 1; i <= n; ++i) {
operations.push_back({ points[i].x, i, 1 });
}
sort(all(operations));
for (auto& o : operations) {
int i = o.i, t = o.t;
if (t == 0) {
ans[i] -= tree.get(querys[i].first.y, querys[i].second.y);
}
else if (t == 1) {
tree.add(points[i].y, 1);
}
else {
ans[i] += tree.get(querys[i].first.y, querys[i].second.y);
}
}
for (int i = 1; i <= m; ++i) {
fout << ans[i] << nl;
}
}