Cod sursa(job #3305634)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 3 august 2025 16:23:09
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include<bits/stdc++.h>
using namespace std;

const int NMAX = 16005;
int n;
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) {
        this->x1 = l1;
        this->y1 = c1;
        this->x2 = l2;
        this->y2 = c2;
    }
};
map<int, int> pozitii;
vector<Point> points;
vector<int> x_uri;
vector<Rectangle> rectangles;
vector<int> aint[NMAX*4];

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].resize(1);
        aint[node][0] = points[left-1].y;
        return;
    }
    int mid = (left+right)/2;
    build(node*2, left, mid);
    build(node*2+1, mid+1, right);

    merge_vectors(aint[node],aint[2*node],aint[2*node+1]);
}
void update() {

}
int query_recursiv(int node, int left, int right,int x1,int x2,int y1,int y2) {
    if (left == x1 && right == x2) {
        return 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_recursiv(node*2, left, mid, x1,x2,y1,y2);
    }
    if (x1 > mid) {
        return query_recursiv(node*2+1, mid+1, right, x1,x2,y1,y2);
    }
    return query_recursiv(2*node,left,mid,x1,mid,y1,y2) + query_recursiv(2*node+1,mid+1,right,mid+1,x2,y1,y2);
}

int query(int x1,int x2,int y1,int y2) {
    return query_recursiv(1,1,n,x1,x2,y1,y2);
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int m;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        points.push_back(Point(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 < x_uri.size(); i++) {
        pozitii[x_uri[i]] = i;
    }

    for (int i = 0; i < n; i++) {
        points[i].x = pozitii[points[i].x]+1;
        printf("%d ",points[i].x);
    }
    printf("\n");


    build(1,1,n);
    scanf("%d", &m);
    for (int i =0;i<m;i++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        Rectangle rectangle(x1, y1, x2, y2);
        rectangles.push_back(rectangle);
    }
    for (int i = 0; i < m; i++) {

        rectangles[i].x1 =  lower_bound(x_uri.begin(), x_uri.end(), rectangles[i].x1) - x_uri.begin() + 1;
        rectangles[i].x2 = upper_bound(x_uri.begin(), x_uri.end(), rectangles[i].x2) - x_uri.begin();

        if (rectangles[i].x2 < rectangles[i].x1) {
            // no points in x range
            rectangles[i].x1 = 1;
            rectangles[i].x2 = 0; // this will ensure query returns 0
        } else {
            rectangles[i].x1 = max(1, min(rectangles[i].x1, n));
            rectangles[i].x2 = max(1, min(rectangles[i].x2, n));
        }

        printf("%d %d\n",rectangles[i].x1,rectangles[i].x2);
    }
    for (auto rect : rectangles) {
        printf("%d\n", query(rect.x1, rect.x2, rect.y1, rect.y2));
    }

    return 0;
}