Cod sursa(job #3342229)

Utilizator ioanabaduIoana Badu ioanabadu Data 23 februarie 2026 14:08:05
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.33 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, lower, upper, mid;

struct point {
    int x, y;
};

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

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

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

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

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

    return left;
}

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

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

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

    return left;
}

int closestSmaller1 (vector <point> a, int val){
    int left, right, middle;
    
    left = 0;
    right = a.size()-1;
    while (left != right){
        middle = (left + right + 1) / 2;

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

    return left;
}

int closestSmaller2 (vector <point> a, int val){
    int left, right, middle;
    
    left = 0;
    right = a.size()-1;
    while (left != right){
        middle = (left + right + 1) / 2;

        if (a[middle].y <= 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){
        lower = closestBigger2(aint[idx], y1);
        upper = closestSmaller2(aint[idx], y2);

        if (upper < lower)
            return 0;

        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;

        lower = closestBigger1(arr, a.x);
        upper = closestSmaller1(arr, b.x);

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