Pagini recente » Cod sursa (job #3238898) | Cod sursa (job #2770704) | Cod sursa (job #3166915) | Cod sursa (job #37256) | Cod sursa (job #3166902)
#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("zoo.in");
ofstream fout("zoo.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;
};
const int nmax = 16000;
const int mmax = 1e5;
int n, m;
point points[nmax + 5];
pair<point, point> querys[mmax + 5];
int ans[mmax + 5]{ 0 };
const int sizemax = nmax + mmax;
struct fenwick {
int t[sizemax + 5]{ 0 };
void add(int i, int x) {
for (; i <= sizemax; 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> normy;
for (int i = 1; i <= n; ++i) {
normy[points[i].y] = 0;
}
for (int i = 1; i <= m; ++i) {
normy[querys[i].first.y] = normy[querys[i].second.y] = 0;
}
for (auto& it : normy) {
static int k = 0;
it.second = ++k;
}
for (int i = 1; i <= n; ++i) {
points[i].y = normy[points[i].y];
}
for (int i = 1; i <= m; ++i) {
querys[i].first.y = normy[querys[i].first.y];
querys[i].second.y = normy[querys[i].second.y];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> points[i].x >> points[i].y;
}
fin >> m;
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;
}
}