Cod sursa(job #3305641)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 3 august 2025 17:19:28
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 16005;

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

struct Rectangle {
    int x1, x2, y1, y2;
    Rectangle(int l1, int c1, int l2, int c2) {
        x1 = l1; y1 = c1; x2 = l2; y2 = c2;
    }
};

vector<Point> points;
vector<int> x_uri;
map<int, int> pozitii;
vector<Rectangle> rectangles;
vector<int> aint[4 * NMAX];
vector<vector<int>> ys;


void merge_vectors(vector<int> &result, const vector<int> &a, const vector<int> &b) {
    result.resize(a.size() + b.size());
    int i = 0, j = 0, k = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] <= b[j])
            result[k++] = a[i++];
        else
            result[k++] = b[j++];
    }
    while (i < (int)a.size()) result[k++] = a[i++];
    while (j < (int)b.size()) result[k++] = b[j++];
}


void build(int node, int left, int right) {
    if (left == right) {
        aint[node] = ys[left];
        sort(aint[node].begin(), aint[node].end());
        return;
    }
    int mid = (left + right) / 2;
    build(node * 2, left, mid);
    build(node * 2 + 1, mid + 1, right);
    merge_vectors(aint[node], aint[node * 2], aint[node * 2 + 1]);
}


int query_rec(int node, int left, int right, int x1, int x2, int y1, int y2) {
    if (x1 > x2) return 0; // invalid range
    if (left == x1 && right == x2) {

        return (int)(upper_bound(aint[node].begin(), aint[node].end(), y2) -
                     lower_bound(aint[node].begin(), aint[node].end(), y1));
    }
    int mid = (left + right) / 2;
    if (x2 <= mid) {
        return query_rec(node * 2, left, mid, x1, x2, y1, y2);
    }
    if (x1 > mid) {
        return query_rec(node * 2 + 1, mid + 1, right, x1, x2, y1, y2);
    }
    return query_rec(node * 2, left, mid, x1, mid, y1, y2) +
           query_rec(node * 2 + 1, mid + 1, right, mid + 1, x2, y1, y2);
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    int n; scanf("%d", &n);
    points.reserve(n);
    x_uri.reserve(n);

    for (int i = 0; i < n; i++) {
        int x, y; scanf("%d %d", &x, &y);
        points.emplace_back(x, y);
        x_uri.push_back(x);
    }


    sort(x_uri.begin(), x_uri.end());
    x_uri.erase(unique(x_uri.begin(), x_uri.end()), x_uri.end());

    for (int i = 0; i < (int)x_uri.size(); i++) {
        pozitii[x_uri[i]] = i + 1;
    }


    for (auto &p : points) {
        p.x = pozitii[p.x];
    }



    int m = (int)x_uri.size();
    ys.assign(m + 1, vector<int>());


    for (auto &p : points) {
        ys[p.x].push_back(p.y);
    }

    build(1, 1, m);

    int q; scanf("%d", &q);
    rectangles.reserve(q);

    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        rectangles.emplace_back(x1, y1, x2, y2);
    }


    for (auto &rect : rectangles) {
        rect.x1 = (int)(lower_bound(x_uri.begin(), x_uri.end(), rect.x1) - x_uri.begin()) + 1;
        rect.x2 = (int)(upper_bound(x_uri.begin(), x_uri.end(), rect.x2) - x_uri.begin());

        int ans = query_rec(1, 1, m, rect.x1, rect.x2, rect.y1, rect.y2);
        printf("%d\n", ans);
    }

    return 0;
}