Bedao Grand Contest 17 - Đếm điểm
Xem dạng PDF
Cho ~n~ điểm ~(x, y)~ nằm trên hệ trục tọa độ, điểm thứ ~i~ có trọng số là ~w_i~.
Cho ~q~ truy vấn, mỗi truy vấn có dạng một số nguyên dương ~r~:
Cho một đường tròn tâm ~(0, 0)~ bán kính ~r~.
Tính tổng trọng số của các điểm nằm trong đường tròn (tính cả các điểm nằm trên đường tròn).
Input
Dòng đầu tiên là 2 số nguyên (~1 \leq n, q \leq 5 \times 10^5~).
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~x, y, w~ cách nhau bởi dấu cách, biểu diễn thông tin của một điểm trên trục tọa độ (~|x|, |y|, |w| \leq 10^9~).
Trong ~q~ dòng tiếp theo, dòng thứ ~j~ (~1 \leq j \leq q~) chứa một số nguyên ~r_j~ (~1 \leq r_j \leq 10^9~) biểu diễn một đường tròn tâm ~(0, 0)~ bán kính ~r_j~.
Output
In ra ~q~ dòng, dòng thứ ~j~ là đáp án cho truy vấn thứ ~j~: tổng trọng số của các điểm nằm trong đường tròn tâm ~(0, 0)~ bán kính ~r_j~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~n, q \le 2000~ |
| 2 | ~30~ | ~w = 1~ |
| 3 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
6 3
-2 -2 1
1 1 2
-1 2 3
2 0 4
0 3 5
1 -3 6
3
2
1
Sample Output 1
15
6
0
Notes
Trong truy vấn ~r=3~, có ~4~ điểm nằm hoàn toàn bên trong đường tròn và ~1~ điểm nằm trên đường tròn ~\Rightarrow~ Đáp án là ~1 + 2 + 3 + 4 + 5 = 15~.
Trong truy vấn ~r=2~, có ~2~ điểm ~(1, 1)~ và ~(2, 0)~ nằm trong đường tròn.
Trong truy vấn ~r=1~, không có điểm nào nằm trong đường tròn.
Bình luận
Thưa admin sao bài này ở sub 2 e dùng hàm upper_bound trong C++ mà khi chạy lại báo sai kết quả là sao ạ ?
bạn để dạng float chưa v
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.