Cod sursa(job #3166806)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 9 noiembrie 2023 17:01:17
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.34 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); }

struct point {
    ll x, y;
    bool operator==(const point& other) const {
        return x == other.x && y == other.y;
    }
};

struct DynamicOrtogonalSegmentTree {
    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;
                    }
                }
            }
        }
    };

    TreeNode* root = new TreeNode;
    pair<point, point> range;

    // 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();
    }

    void add(point pos) { add(root, range, pos); }

    // 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 get(pair<point, point> query) { return get(root, range, query); }
} tree;

int n, m;
int max_coord_x = 0, max_coord_y = 0;
vector<point> points;
vector<pair<point, point>> querys;

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];
    }
    max_coord_x = normx.rbegin()->second;
    max_coord_y = normy.rbegin()->second;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n;
    points.resize(n);
    for (auto& p : points) {
        fin >> p.x >> p.y;
    }
    fin >> m;
    querys.resize(m);
    for (auto& q : querys) {
        fin >> q.first.x >> q.first.y >> q.second.x >> q.second.y;
    }
    normalizeInput();
    tree.range = {
        point{ 0, 0 },
        point{ max_coord_x, max_coord_y }
    };
    for (auto& p : points) {
        tree.add(p);
    }
    for(auto& q : querys) {
        fout << tree.get(q) << nl;
    }
}