Cod sursa(job #2740801)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 aprilie 2021 13:04:15
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MOD 1000000007
using namespace std;

const int INF = (1 << 30), NMAX(100005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

struct Kdtree{
    int n;
    vector<Point> v;

    Kdtree(vector<Point> v): n(v.size()), v(v){
        build(0, n, 0);
    }

    void build(int st, int dr, int tip){
        if(dr <= st)
            return;
        int mij = (st + dr) / 2;
        nth_element(v.begin() + st, v.begin() + mij, v.begin() + dr, [&](Point &a, Point& b) {return a[tip] < b[tip];});
        build(st, mij, !tip);
        build(mij + 1, dr, !tip);
    }

    int Count(Point cJ, Point cS){
        int rez = 0;
        auto go = [&](auto &self, int st, int dr, int tip){
            if(dr <= st)
                return;
            int mij = (st + dr) / 2;
            auto &q = v[mij];
            if(cJ[0] <= q[0] && q[0] <= cS[0] && cJ[1] <= q[1] && q[1] <= cS[1])
                ++rez;
            if(cJ[tip] <= q[tip])
                self(self, st, mij, !tip);
            if(q[tip] <= cS[tip])
                self(self, mij + 1, dr, !tip);
        };
        go(go, 0, n, 0);
        return rez;
    }
};

int main()
{
    BUNA("zoo");
    int n;
    cin >> n;

    vector<Point> p(n);
    vector<int> v;
    for(int i = 0; i < n; ++i){
        cin >> p[i][0] >> p[i][1];
        v.push_back(p[i][0]);
    }

    sort(v.begin(), v.end());

    Kdtree Arb(p);
    int q;
    cin >> q;

    while(q--){
        Point a, b;
        cin >> a[0] >> a[1] >> b[0] >> b[1];

        int x1 = lower_bound(v.begin(), v.end(), a[0]) - v.begin() + 1;
        int x2 = upper_bound(v.begin(), v.end(), b[0]) - v.begin();
        if(1 <= x1 && x2 <= n)
            cout << Arb.Count(a, b) << '\n';
        else cout << 0 << '\n';
    }
    PA();
}