Pagini recente » Cod sursa (job #2886855) | Cod sursa (job #3237796) | Borderou de evaluare (job #2029654) | Cod sursa (job #2339875) | Cod sursa (job #3165296)
#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); }
int n, m;
struct TreeNode {
TreeNode* children[2][2];
int value;
TreeNode() {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
children[i][j] = nullptr;
}
}
value = 0;
}
void compute() {
value = 0;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
if (children[i][j] != nullptr) {
value += children[i][j]->value;
}
}
}
}
};
struct point {
ll x, y;
bool operator==(const point& other) const {
return x == other.x && y == other.y;
}
};
// add a point to the 2D dynamic segment tree
void add(TreeNode* root, pair<point, point> curr, point pos) {
// found it
if (curr.first == pos && curr.second == pos) {
root->value++;
return;
}
ll midx = (curr.first.x + curr.second.x) / 2;
ll midy = (curr.first.y + curr.second.y) / 2;
pair<point, point> next;
if (pos.x <= midx) {
next.first.x = curr.first.x;
next.second.x = midx;
}
else {
next.first.x = midx + 1;
next.second.x = curr.second.x;
}
if (pos.y <= midy) {
next.first.y = curr.first.y;
next.second.y = midy;
}
else {
next.first.y = midy + 1;
next.second.y = curr.second.y;
}
if (root->children[pos.y > midy][pos.x > midx] == nullptr) {
root->children[pos.y > midy][pos.x > midx] = new TreeNode;
}
add(root->children[pos.y > midy][pos.x > midx], next, pos);
root->compute();
}
// get the number of points in a 2D range
int get(TreeNode* root, pair<point, point> curr, pair<point, point> query) {
// empty
if (root == nullptr) {
return 0;
}
// outside of query
if (curr.second.x < query.first.x || curr.first.x > query.second.x
|| curr.second.y<query.first.y || curr.first.y>query.second.y) {
return 0;
}
// inside of query
if (query.first.x <= curr.first.x && curr.second.x <= query.second.x
&& query.first.y <= curr.first.y && curr.second.y <= query.second.y) {
return root->value;
}
// curr intersects query
ll midx = (curr.first.x + curr.second.x) / 2;
ll midy = (curr.first.y + curr.second.y) / 2;
return get(root->children[0][0], { curr.first, { midx, midy } }, query) +
get(root->children[0][1], { { midx + 1, curr.first.y }, { curr.second.x, midy } }, query) +
get(root->children[1][0], { { curr.first.x, midy + 1 }, { midx, curr.second.y } }, query) +
get(root->children[1][1], { { midx + 1, midy + 1 }, curr.second }, query);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n;
TreeNode* root = new TreeNode;
pair<point, point> range{
point{ 0, 0 },
point{ 4000000000, 4000000000 }
};
for (int i = 1; i <= n; ++i) {
ll x, y;
fin >> x >> y;
x += 2000000000;
y += 2000000000;
add(root, range, point{ x, y });
}
fin >> m;
while (m--) {
pair<point, point> query;
fin >> query.first.x >> query.first.y >> query.second.x >> query.second.y;
query.first.x += 2000000000;
query.first.y += 2000000000;
query.second.x += 2000000000;
query.second.y += 2000000000;
fout << get(root, range, query) << nl;
}
}