Trọng số khoản
Xem PDF
Điểm:
500 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy.
Ví dụ trọng số của dãy \((3,1,7,2)\) là \(6\), trọng số của dãy \((40,40)\) là \(0\).
Yêu cầu: Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\). Hãy tính tổng trọng số của tất cả các dãy con gồm các phần tử liên tiếp trong \(𝐴\).
Ví dụ với \(𝐴 = (1,2,3)\), những dãy con gồm các phần tử liên tiếp trong \(𝐴\) là:
- Dãy rỗng và các dãy (1), (2), (3): trọng số 0
- Dãy \((1,2)\) và dãy \((2,3)\): trọng số \(1\)
- Dãy \((1,2,3)\): trọng số \(2\)
=> Tổng trọng số cần tìm: \(4\)
Input
- Dòng 1 chứa số nguyên dương \(𝑛 \leq 4 \times 10^5\)
- Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) có giá trị không vượt quá \(10^6\).
Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách.
Output
- Ghi ra một số nguyên duy nhất là kết quả tìm tìm được
Scoring
- Subtask \(1\) (\(32.5\%\) số điểm): \(𝑛 \leq 4 \times 10^2\)
- Subtask \(2\) (\(20\%\) số điểm): \(𝑛 \leq 10^4\)
- Subtask \(3\) (\(47.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\)
Example
Test 1
Input
3
1 2 3 Output
4Test 2
Input
4
3 1 7 2 Output
31
Bình luận
solution bài này có vẻ dễ hơn mình tưởng
-
0
TLight
9:39 p.m. 16 Tháng 11, 2022
-
0
huyhau6a2
5:42 a.m. 17 Tháng 11, 2022
←
chỉnh sửa 3
→
-
0
TLight
2:49 p.m. 17 Tháng 11, 2022
-
1
huyhau6a2
5:06 p.m. 17 Tháng 11, 2022
3 bình luận nữaxem solution ở đâu vậy bạn?
Mình làm segment tree không dùng stack deque nên time lâu hơn nhiều. Lúc đầu mình làm segment tree xong xem code ngưòi khác ra stackd deque nên mới nói thế nha!
Không. Tớ hỏi là xem bài làm của người khác ở đâu ý :>
Tớ mới dùng nên chưa quen
Bạn phải ac mới được xem nha