Cod sursa(job #3271216)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 25 ianuarie 2025 14:06:20
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 16005, VAL_MAX = 2e9 + 10;
int N, maxX, maxY, nrX, nrY;

struct Point
{
    int x, y;
};

Point points[N_MAX];
vector<int> xList[N_MAX];
pair<int, int> SortedX[N_MAX], SortedY[N_MAX];

struct SegmentTree_2D
{
    vector<int> A[4 * N_MAX];

    int x1, y1, x2, y2; /// for query

    void Build(int node, int L, int R)
    {
        if(L == R)
        {
            // A[node].SortedPoints = xList[L];
            swap(A[node], xList[L]);
            return;
        }

        int m = (L + R) / 2;
        Build(2 * node, L, m);
        Build(2 * node + 1, m + 1, R);

        // A[node] = A[2 * node] + A[2 * node + 1];
        merge(A[2 * node].begin(), A[2 * node].end(),
              A[2 * node + 1].begin(), A[2 * node + 1].end(),
              back_inserter(A[node]));
    }

    int Query(int x1, int y1, int x2, int y2)
    {
        this->x1 = x1;
        this->y1 = y1;
        this->x2 = x2;
        this->y2 = y2;

        return Query(1, 1, maxX);
    }

    int Query(int node, int L, int R)
    {
        if(x1 <= L && R <= x2)
        {
            return upper_bound(A[node].begin(), A[node].end(), y2)
                   - upper_bound(A[node].begin(), A[node].end(), y1 - 1);
        }

        int m = (L + R) / 2;
        int res = 0;

        if(x1 <= m)
            res += Query(2 * node, L, m);
        if(m < x2)
            res += Query(2 * node + 1, m + 1, R);

        return res;
    }
} tree;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N;

    for(int i = 0; i < N; i++)
        cin >> points[i].x >> points[i].y;
}

void Normalize()
{
    /// Sort by X

    int i, j, crr;

    sort(points, points + N, [&](const Point a, const Point b){
            return a.x < b.x || (a.x == b.x && a.y < b.y);
         });

    for(i = 0, j = 0, crr = 1; i < N; i++, j++, crr++)
    {
        SortedX[j] = make_pair(points[i].x, crr);

        while(i < N && points[i].x == points[i+1].x)
        {
            points[i].x = crr;
            i++;
        }
        points[i].x = crr;
    }

    maxX = crr;
    nrX = j + 1;
    SortedX[j] = make_pair(VAL_MAX, maxX);

    /// Sort by Y

    sort(points, points + N, [&](const Point a, const Point b){
            return a.y < b.y || (a.y == b.y && a.x < b.x);
         });

    for(i = 0, j = 0, crr = 1; i < N; i++, j++, crr++)
    {
        SortedY[j] = make_pair(points[i].y, crr);

        while(i < N && points[i].y == points[i+1].y)
        {
            points[i].y = crr;
            xList[points[i].x].push_back(crr);
            i++;
        }
        points[i].y = crr;
        xList[points[i].x].push_back(crr);
    }

    maxY = crr;
    nrY = j + 1;
    SortedY[j] = make_pair(VAL_MAX, maxY);
}

void Solve()
{
    int Q, x1, y1, x2, y2;

    cin >> Q;

    while(Q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;

        x1 = lower_bound(SortedX, SortedX + nrX, make_pair(x1, 0))->second;
        y1 = lower_bound(SortedY, SortedY + nrY, make_pair(y1, 0))->second;
        x2 = lower_bound(SortedX, SortedX + nrX, make_pair(x2 + 1, 0))->second - 1;
        y2 = lower_bound(SortedY, SortedY + nrY, make_pair(y2 + 1, 0))->second - 1;

        cout << tree.Query(x1, y1, x2, y2) << '\n';
    }
}

int main()
{
    SetInput("zoo");

    ReadInput();
    Normalize();
    tree.Build(1, 1, maxX);
    Solve();

    return 0;
}