Cod sursa(job #3162284)

Utilizator divadddDavid Curca divaddd Data 28 octombrie 2023 19:36:04
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int NMAX = 16e3+2;
int n,q;
pii a[NMAX];

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

struct Node {
    vector<int> v;
    int xl, xr;

    Node operator + (const Node &aux) const {
        Node ans;
        ans.v.resize(v.size() + aux.v.size());
        int i = 0, j = 0, k = 0;
        while(i < v.size() && j < aux.v.size()){
            if(v[i] < aux.v[j]){
                ans.v[k++] = v[i++];
            }else{
                ans.v[k++] = aux.v[j++];
            }
        }
        while(i < v.size()){
            ans.v[k++] = v[i++];
        }
        while(j < aux.v.size()){
            ans.v[k++] = aux.v[j++];
        }
        ans.xl = xl;
        ans.xr = aux.xr;
        return ans;
    }
} aint[4*NMAX];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].v.push_back(a[st].second);
        aint[nod].xl = aint[nod].xr = a[st].first;
    }else{
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

int cnt(int nod, int l, int r){
    /// cate nr sunt intre l si r in aint[nod].v
    int st = 0, dr = aint[nod].v.size()-1;
    int rbound = -1;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(aint[nod].v[mid] <= r){
            rbound = mid;
            st = mid+1;
        }else{
            dr = mid-1;
        }
    }
    int lbound = -1;
    st = 0, dr = aint[nod].v.size()-1;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(aint[nod].v[mid] >= l){
            lbound = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    if(lbound == -1 || rbound == -1){
        return 0;
    }
    return rbound-lbound+1;
}

int query(int nod, int st, int dr, int xl, int xr, int yl, int yr){
    if(aint[nod].xr < xl){
        return 0;
    }
    if(aint[nod].xl > xr){
        return 0;
    }
    if(xl <= aint[nod].xl && aint[nod].xr <= xr){
        return cnt(nod, yl, yr);
    }else{
        int mid = (st+dr)/2;
        int ans = 0;
        if(xl <= aint[2*nod].xr){
            ans += query(2*nod, st, mid, xl, xr, yl, yr);
        }
        if(xr >= aint[2*nod+1].xl){
            ans += query(2*nod+1, mid+1, dr, xl, xr, yl, yr);
        }
        return ans;
    }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> a[i].first >> a[i].second;
    }
    sort(a+1, a+n+1);
    build(1, 1, n);
    fin >> q;
    while(q--){
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        fout << query(1, 1, n, x1, x2, y1, y2) << "\n";
    }
    return 0;
}