Tổng trọng số điểm trong hình chữ nhật

General
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved