Cod sursa(job #3165296)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 5 noiembrie 2023 20:16:55
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.08 kb
#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;
    }
    
}