1
class Solution {
2
  void buildTree(vector<vector<int>> &p, int depth, int i, int j) {
3
    if (j - i <= 1) return;
4

5
    int k = 1 - depth & 1, m = i + (j - i) / 2;
6
    nth_element(p.begin() + i, p.begin() + m, p.begin() + j,
7
                [k](auto &a, auto &b) { return a[k] < b[k]; });
8
    partition(p.begin() + i, p.begin() + j, [k, m, &p](auto &a) { return a[k] < p[m][k]; });
9

10
    buildTree(p, depth + 1, i, m);
11
    buildTree(p, depth + 1, m + 1, j);
12
  }
13

14
  inline bool isPointInside(const vector<int> &p, const vector<int> &c) {
15
    return (p[0] - c[0]) * (p[0] - c[0]) + (p[1] - c[1]) * (p[1] - c[1]) <= c[2] * c[2];
16
  }
17

18
  int pointsInside(const vector<vector<int>> &t, const vector<int> &q, int depth, int i, int j) {
19
    if (j == i)
20
      return 0;
21
    else if (j - i == 1)
22
      return isPointInside(t[i], q);
23

24
    int k = 1 - depth & 1, m = i + (j - i) / 2, diff = t[m][k] - q[k];
25
    if (diff > q[2])
26
      return pointsInside(t, q, depth + 1, i, m);
27
    else if (diff < -q[2])
28
      return pointsInside(t, q, depth + 1, m + 1, j);
29
    else
30
      return pointsInside(t, q, depth + 1, i, m) + isPointInside(t[m], q) +
31
             pointsInside(t, q, depth + 1, m + 1, j);
32
  }
33

34
 public:
35
  vector<int> countPoints(vector<vector<int>> &points, vector<vector<int>> &queries) {
36
    buildTree(points, 0, 0, points.size());
37

38
    vector<int> res(queries.size());
39
    for (size_t i = 0; i < queries.size(); ++i)
40
      res[i] = pointsInside(points, queries[i], 0, 0, points.size());
41
    return res;
42
  }
43
};