Tượng Đài Bác Hồ - LCOJ: Luyện Code Online Judge

TUONGDAI - Tượng Đài Bác Hồ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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

Output #1

15 9

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

0

DenisPham đã bình luận lúc 7, Tháng 2, 2026, 2:56

include<bits/stdc++.h>

using namespace std;

int main(){ long long n, k; cin >> n >> k; long long a[n]; for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<long long> prefix(n + 1, 0); for(int i = 1; i <= n; i++){ prefix[i] = prefix[i - 1] + a[i]; } while(k--){ long long u, v; cin >> u >> v; cout << prefix[v] - prefix[u - 1] << " "; } }

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(NULL);

int n, k;
cin >> n >> k;
vector&lt;long long> w(n+1);
for (int i = 1; i <= n; i++) {
    cin >> w[i];
}

// prefix sum
vector&lt;long long> pref(n+1);
pref[0] = 0;
for (int i = 1; i <= n; i++) {
    pref[i] = pref[i-1] + w[i];
}

while (k--) {
    int u, v;
    cin >> u >> v;
    long long result = pref[v] - pref[u-1];
    cout << result;
    if (k) cout << ' ';
}
cout << '\n';
return 0;

}

4

0988440189 đã bình luận lúc 19, Tháng 4, 2025, 10:26

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...

0

Bach2013 đã bình luận lúc 8, Tháng 5, 2025, 15:29

cảm ơn bạn rất nhiều