Cod sursa(job #3183134)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 10 decembrie 2023 19:13:37
Problema Zoo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
const int NMAX = 16002;
vector<pair<int, int>> p;
struct Query{
    int x1, y1, x2, y2;
    int index;
    bool operator<(const Query& other) const {
        return x2 < other.x2;
    }
};
vector<vector<int>> aint(4 * NMAX);
void build(int nod, int l, int r){
    if(l == r){
        aint[nod] = vector<int>(1, p[l].second);
        return;
    }
    
    const int mid = (l + r) / 2;
    build(2 * nod, l, mid);
    build(2 * nod + 1, mid+1, r);

    int i = 0, j = 0;
    vector<int>* left = &aint[2 * nod];
    vector<int>* right = &aint[2 * nod + 1];

    aint[nod].clear();

    while(i < (*left).size() and j < (*right).size()){
        if((*left)[i] <= (*right)[j])
            aint[nod].push_back((*left)[i++]);
        
        else aint[nod].push_back((*right)[j++]);
    }

    while(i < (*left).size())
        aint[nod].push_back((*left)[i++]);

    while(j < (*right).size())
        aint[nod].push_back((*right)[j++]);
}

int upper_bound(vector<int> v, int val){
    int l = 0, r = v.size() - 1, sol = v.size();

    while(l <= r){
        int mid = (l + r) / 2;
        if(v[mid] > val)
            sol = mid, r = mid - 1;
        
        else l = mid + 1;
    }

    return sol;
}
int lower_bound(int r, const int val){
    int l = 1, sol = r + 1;

    while(l <= r){
        const int mid = (l + r) / 2;

        if(p[mid].first >= val)
            sol = mid, r = mid - 1;
        
        else l = mid + 1;
    }

    return sol;
}
int query(int nod, int l, int r, int x, int y, int val){
    if(l == r)
        return aint[nod][0] <= val;
    
    if(l == x and r == y)
        return upper_bound(aint[nod], val);
    
    const int mid = (l + r) / 2;
    if(y <= mid)
        return query(2 * nod, l, mid, x, y, val);
    
    else if(x > mid)
        return query(2 * nod + 1, mid + 1, r, x, y, val);
    
    return query(2 * nod, l, mid, x, mid, val) + query(2 * nod + 1, mid + 1, r, mid + 1, y, val);
}
int main(){
    int n, m;
    cin>>n;
    p.resize(n+1);
    for(int i=1; i<=n; i++)
        cin>>p[i].first>>p[i].second;
    

    cin>>m;
    vector<Query> q(m);
    for(int i=0; i<m; i++)
        cin>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2, q[i].index = i;
    
    sort(p.begin() + 1, p.end());
    sort(q.begin(), q.end());

    vector<int> answers(m);

    build(1, 1, n);
    int x = 1;
    for(int i=0; i<m; i++){
        while(x <= n and p[x].first <= q[i].x2)
            x++;
        
        if(x == 1)
            continue;

        int st = lower_bound(x-1, q[i].x1);
        if(st == x)
            continue;

        int upper = query(1, 1, n, st, x-1, q[i].y2);
        int lower = query(1, 1, n, st, x-1, q[i].y1 - 1);
        answers[q[i].index] = upper - lower;
    }

    for(int i=0; i<m; i++)
        cout<<answers[i]<<'\n';

    return 0;
}