TUONGDAI - Tượng Đài Bác Hồ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Thành Phố Sơn La đang khởi công xây dựng khu Tượng Đài Bác Hồ. Để san lấp mặt bằng, Ban Quản Lý dự án đã huy động các xe tải chở đất từ các ngọn đồi xung quanh Thành Phố về đổ vào đây. Cán bộ giám sát thi công đã ghi được danh sách ~n~ xe đất, đánh số từ ~1~ đến ~n~. Xe thứ ~i~ chở được khối lượng đất là số nguyên không âm ~w_i~ ~(dm^3)~. Để thanh toán tiền cho các đội xe, Ban Quản Lý dự án có ~k~ cặp số nguyên dương ~u, v~, với mỗi cặp số ~u, v~ cần tính tổng khối lượng đất của các xe từ chỉ số ~u~ đến chỉ số ~v~ (tức là ~w_u + w_{u + 1} + … + w_v~). Bạn hãy lập chương trình giúp Ban Quản Lý dự án tính các tổng này.
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~k~;
- Dòng thứ hai chứa ~n~ số nguyên không âm ~w_1, w_2, …, w_n~;
- ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ n, k ≤ 10^5; 1 ≤ u ≤ v ≤ n; 0 ≤ w_i ≤ 10^5~.
Output
- Ghi trên một dòng ~k~ số nguyên theo thứ tự là đáp số của bài toán ứng với ~k~ cặp số ~u, v~. Hai số liên tiếp được ghi cách nhau một dấu cách.
Sample
Input #1
5 2
1 2 3 4 5
1 5
2 4
Output #1
15 9
Problem source: Chuyên Sơn La Online Judge
Bình luận
Ae làm bài này theo tư tưởng PreFixSum nhé , nghĩa là mình sẽ lưu tổng thằng S[i-1] , rồi thằng S[i]=S[i-1]+a[i].Xong lấy S[r]- S[l-1]là ra nhé .Viết hơi vội nên có thể sai nhưng tư tưởng như thế là đúng , có j ae chỉnh lại i với j nhé. Fan MU mãi đỉnh...