Bedao Regular Contest 11 - H2O
View as PDFBạn được cho ~N~ thùng nước, thùng nước thứ ~i~ nằm ở vị trí ~X[i]~ và chứa ~W[i]~ lít nước ~(1 \le i \le n)~, các vị trí của những thùng nước được sắp xếp tăng dần . Chí phí vận chuyển thùng nước thứ ~i~ về thùng nước thứ ~j~ là ~W[i] \times (X[j] - X[i] ) ~ ~(1 \le i < j \le N)~.
Bạn có ~Q~ truy vấn mỗi truy vấn bạn cần phải tìm tổng chi phí để vận chuyển các thùng nước thứ ~l~ đến ~r-1~ về thùng nước thứ ~r~.
Input
Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \le N \le 10^{6})~. ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số cách nhau bới dấu cách là tọa độ ~X[i]~ và lượng nước ~W[i]~ của thùng nước thứ ~i~ ~(1 \le X[i] , W[i] \le 10^{6})~ .
Dòng thứ ~N + 1~ số lượng truy vấn ~Q~ ~(1 \le Q \le 10^{6})~. ~Q~ dòng tiếp theo mỗi dòng chứa hai số ~L~ và ~R~ cách nhau bởi dấu cách là dữ liệu cho từng truy vấn .
Output
Ghi ra ~Q~ dòng lần lượt là câu trả lời của từng truy vấn .
Subtask
- ~50\%~ số test có ~ 1 \le N , Q \le 1000~.
- Còn lại không có điều kiện gì thêm
Sample Input
3
1 20
2 20
3 20
2
1 2
1 3
Sample Output
20
60
Note
Truy vấn ~1~ ~(2 - 1) \times 20~.
Truy vấn ~2~ ~(3 - 1) \times 20 + (3 - 2) \times 20~.
Comments
Mn ơi, bài này em code tối ưu rk mà chx AC ls ạ :(((
This comment is hidden due to too much negative feedback. Show it anyway.
bạn đổi endl thành "\n" nhé
bạn đổi endl thành "\n" nhé
This comment is hidden due to too much negative feedback. Show it anyway.