Subtask 1

Với mỗi truy vấn ~q_j~, ta duyệt tất cả các điểm rồi tính khoảng cách từ ~(x,y)~ đến ~(0,0)~ rồi lấy khoảng cách so sánh với ~r~. Gọi ~d~ là khoảng cách giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~. Ta có: $$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$.

Độ phức tạp: ~O(n \cdot q)~

Subtask 2

Khi ~w_i = 1~ thì đề bài trở thành bài toán đếm số lượng điểm trong đường tròn. Theo công thức tính khoảng cách ~d~ ở trên, ta có một nhận xét là khoảng cách giữa ~(x,y)~ và ~(0,0)~ là độ dài bán kính của đường tròn đồng tâm ~(0,0)~ với độ lớn ~|\vec{u}(x,y)|~. Hay: $$d = \sqrt{(x - 0)^2 + (y - 0)^2} = \sqrt{x^2 + y^2} = |\vec{u}(x,y)|$$.

Thay vì ta có ~n~ điểm có tọa độ ~(x_i, y_i)~, ta có ~n~ đường tròn tâm ~(0,0)~ với bán kính có độ lớn là ~|\vec{u}(x_i,y_i)|~.

Từ đó, ta có thể sắp xếp lại các đường tròn (các điểm) theo bán kính với độ lớn ~\sqrt{{x_i}^2 + {y_i}^2}~. Để tránh việc sử dụng số thực, thay vì ta so sánh ~\sqrt{x^2 + y^2}~ với ~r~, ta so sánh ~x^2 + y^2~ với ~r^2~. Vậy điều đó có nghĩa là ta sắp xếp lại các đường tròn theo bình phương bán kính với độ lớn ~{x_i}^2 + {y_i}^2~.

Sau khi các "đường tròn" đã được sắp xếp, với mỗi truy vấn ~q_j~, ta tìm kiếm nhị phân đến đường tròn có bình phương bán kính lớn nhất nhỏ hơn hoặc bằng ~r^2~. Kết quả là chỉ số của đường tròn đó (với chỉ số bắt đầu từ 1).

Độ phức tạp: ~O(n \cdot log(n) + q \cdot log(n))~

Subtask 3

Thực hiện sắp xếp và tìm kiếm nhị phân như subtask 2, nhưng sau khi sắp xếp, ta sử dụng một mảng cộng dồn với giá trị là tổng các trọng số ~w_i~ trên từng đoạn. Kết quả là giá trị của mảng cộng dồn tại chỉ số của "đường tròn" có bình phương bán kính lớn nhất nhỏ hơn hoặc bằng ~r^2~.

Độ phức tạp: ~O(n \cdot log(n) + q \cdot log(n))~

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
#ifndef LOCAL
  std::cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

  int n, tt;
  std::cin >> n >> tt;
  std::vector<int> x(n), y(n), w(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> x[i] >> y[i] >> w[i];
  }

  std::vector<std::pair<int64_t, int>> dist(n);
  for (int i = 0; i < n; ++i) {
    dist[i].first = (int64_t)x[i] * x[i] + (int64_t)y[i] * y[i];
    dist[i].second = w[i];
  }
  std::sort(dist.begin(), dist.end());

  std::vector<int64_t> pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + dist[i].second;
  }

  while (tt--) {
    int64_t radius;
    std::cin >> radius;
    radius *= radius;
    int ans = -1;
    int low = 0, high = n - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (dist[mid].first <= radius) {
        ans = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    std::cout << pref[ans + 1] << '\n';
  }

  return 0;
}