Plundering Pirates - BIO 2025 Round 2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void inputOutput() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef EREKLE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}

long long INF = 1e10;

struct FenwickTree {
    int n;
    vector<int> fenwick;
    FenwickTree(int len): n(len) {
        fenwick.resize(n);
    }
    void update(int index, int value) {
        while (index < n) {
            fenwick[index] += value;
            index += index & -index;
        }
    }
    int read(int index) {
        int sum = 0;
        while (index > 0) {
            sum += fenwick[index];
            index -= index & -index;
        }
        return sum;
    }
    int range(int left, int right) { // (l, r]
        return read(right) - read(left);
    }
};

struct Subquery {
    int right; // left will be 0
    int bottom, top;
    int queryIndex;
    int sign; // -1 or +1
    Subquery(int r, int b, int t, int i, int s): right(r), bottom(b), top(t), queryIndex(i), sign(s) {}
};

int main() {
    inputOutput();
    int p, r; cin >> p >> r;
    vector<long long> x(p), y(p);
    vector<pair<pair<int, int>, pair<int, int>>> rectangles(r);
    int maxY;

    // input co-ordinates and compress y
    {
        for (int i = 0; i < p; ++i) cin >> x[i] >> y[i];

        vector<long long> u = y;
        u.push_back(-1);
        u.push_back(INF);
        sort(u.begin(), u.end());
        u.resize(unique(u.begin(), u.end()) - u.begin());
        for (long long &i : y) {
            i = lower_bound(u.begin(), u.end(), i) - u.begin();
        }
        for (int i = 0; i < r; ++i) {
            auto & [x1, y1] = rectangles[i].first;
            auto & [x2, y2] = rectangles[i].second;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 > x2) swap(x1, x2);
            if (y1 > y2) swap(y1, y2);

            y1 = lower_bound(u.begin(), u.end(), y1) - u.begin();
            y2 = upper_bound(u.begin(), u.end(), y2) - u.begin() - 1;
        }
        maxY = u.size();
    }

    vector<Subquery> subqueries;
    for (int i = 0; i < r; ++i) {
        // express the sum inside this rectangle as the difference between sums inside two rectangles
        auto [x1, y1] = rectangles[i].first;
        auto [x2, y2] = rectangles[i].second;
        subqueries.emplace_back(x2, y1, y2, i, +1);
        subqueries.emplace_back(x1-1, y1, y2, i, -1);
    }
    // sort subqueries by right (x)
    sort(subqueries.begin(), subqueries.end(), [](const Subquery & q1, const Subquery & q2) {
        return q1.right < q2.right;
    });

    vector<pair<int, int>> points(p);
    for (int i = 0; i < p; ++i) points[i] = {x[i], y[i]};
    // sort points by x
    sort(points.begin(), points.end());

    // iterate subqueries and points left-to-right with two pointers
    FenwickTree fenwickTree(maxY);
    vector<int> queryAnswers(r);
    size_t nextPoint = 0, nextQuery = 0;
    auto answerQueries = [&]() {
        while (nextQuery < subqueries.size() && (nextPoint >= points.size() || subqueries[nextQuery].right < points[nextPoint].first)) {
            if (nextQuery >= subqueries.size()) exit(0);
            int d = fenwickTree.range(subqueries[nextQuery].bottom-1, subqueries[nextQuery].top);
            queryAnswers[subqueries[nextQuery].queryIndex] += subqueries[nextQuery].sign * d;
            nextQuery++;
        }
    };

    while (nextPoint < points.size()) {
        answerQueries();
        // add next point to data structure
        fenwickTree.update(points[nextPoint].second, +1);
        ++nextPoint;
    }
    answerQueries();

    for (int v : queryAnswers) cout << v << '\n';
    return 0;
}