Cod sursa(job #3342218)

Utilizator ioanabaduIoana Badu ioanabadu Data 23 februarie 2026 13:50:44
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 16005

using namespace std;

ifstream in("zoo.in");
ofstream out("zoo.out");

int animals, queries;

struct point {
    int x, y;
};

vector <point> aint[NMAX*2], arr;

bool comp (point a, point b){
    return a.x < b.x;
}

int closestBigger (vector <point> a, int val, int flag){
    int left, right, middle;

     vector <int> b;
    for (auto i:a){
        if (flag == 0)
            b.push_back(i.x);
        else
            b.push_back(i.y);
    }

    left = 0;
    right = b.size()-1;
    while (left != right){
        middle = (left + right) / 2;

        if (b[middle] < val)
            left = middle + 1;
        else
            right = middle;
    }

    return left;
}

int closestSmaller (vector <point> a, int val, int flag){
    int left, right, middle;
    
    vector <int> b;
    for (auto i:a){
        if (flag == 0)
            b.push_back(i.x);
        else
            b.push_back(i.y);
    }

    left = 0;
    right = b.size()-1;
    while (left != right){
        middle = (left + right + 1) / 2;

        if (b[middle] <= val)
            left = middle;
        else
            right = middle - 1;
    }

    return left;
}

void create (int idx, int a, int b){
    if (a == b){
        aint[idx].push_back(arr[a]);
        return;
    }

    int mid = (a+b)/2;
    create(idx*2, a, mid);
    create(idx*2+1, mid+1, b);

    int size1, size2, i, j;

    size1 = aint[idx*2].size();
    size2 = aint[idx*2+1].size();
    i = 0, j = 0;

    while (i<size1 && j<size2){
        if (aint[idx*2][i].y < aint[idx*2+1][j].y)
            aint[idx].push_back(aint[idx*2][i++]);
        else
            aint[idx].push_back(aint[idx*2+1][j++]);
    }

    while (i < size1)
        aint[idx].push_back(aint[idx*2][i++]);

    while (j < size2)
        aint[idx].push_back(aint[idx*2+1][j++]);
}

int query (int idx, int left, int right, int idx1, int idx2, int y1, int y2){
    if (right < idx1 || left > idx2)
        return 0;
    if (left >= idx1 && right <= idx2){
        int lower = closestBigger(aint[idx], y1, 1);
        int upper = closestSmaller(aint[idx], y2, 1);

        return upper - lower + 1;
    }
    int mid = (left + right)/2;

    return query(idx*2, left, mid, idx1, idx2, y1, y2) 
        + query(idx*2+1, mid+1, right, idx1, idx2, y1, y2);
}

int main (){
    in >> animals;
    arr.resize(animals);
    for (int i=0; i<animals; ++i){
        in >> arr[i].x >> arr[i].y;
    }

    sort (arr.begin(), arr.end(), comp);
    create(1, 0, animals-1);
    
    point a, b;
    in >> queries;
    while (queries--){
        in >> a.x >> a.y >> b.x >> b.y;

        int lower = closestBigger(arr, a.x, 0);
        int upper = closestSmaller(arr, b.x, 0);

        out << query(1, 0, animals-1, lower, upper, a.y, b.y) << '\n';
    }

    return 0;
}