Tổng trọng số điểm trong hình chữ nhật
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Trên mặt phẳng tọa độ $Oxy$ cho $N$ điểm, điểm thứ $i$ có tọa độ $(x_i, y_i)$ và trọng số $w_i$. Cho $Q$ truy vấn, mỗi truy vấn là một hình chữ nhật có các cạnh song song với trục tọa độ, xác định bởi góc dưới trái $(x_1, y_1)$ và góc trên phải $(x_2, y_2)$ ($x_1 \le x_2, y_1 \le y_2$). Hãy tính tổng trọng số của tất cả các điểm nằm trong hoặc trên biên của hình chữ nhật đó.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $Q$.
- $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i, y_i, w_i$.
- $Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_1, y_1, x_2, y_2$.
Dữ liệu ra
Gồm $Q$ dòng, mỗi dòng in ra tổng trọng số cho truy vấn tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 4 2 1 1 5 2 3 10 4 2 3 3 4 7 1 1 3 3 2 2 5 5 |
15 20 |
Giới hạn
- $1 \le N, Q \le 10^5$
- $-10^9 \le x_i, y_i, x_1, y_1, x_2, y_2 \le 10^9$
- $-10^6 \le w_i \le 10^6$
Community Discussion