Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P131SUMG - SUM1 G - Giá trị của dãy số

Định nghĩa giá trị của dãy số là sự chênh lệch giữa số lớn nhất và nhỏ nhất trong dãy. Ví dụ,  giá trị của dãy (3, 1, 7, 2) là 6, và giá trị của (42, 42) là 0.

Tìm tổng của các giá trị của tất cả các dãy con chứa các phần tử liên tiếp trong dãy số đã cho.

Input

Dòng đầu tiên của input chứa một số nguyên N ( 2<= N <= 300 000), số phần tử của dãy.
N dòng tiếp theo chứa các phần tử của dãy số. Mỗi phần tử là một số nguyên dương không lớn hơn 100 000 000.

Output

In ra một số nguyên là đáp số của bài toán.

Example

Test 1.
Input:
3
1
2
3

Ouput:
4


Test 2.
Input:
4
7
5
7
5

Ouput:
12


Test 3.
Input:
4
3
1
7
2

Ouput:
31

Giải thích test 3:

-Các tập con có 1 phần tử có độ chênh lệch bằng 0
-Các tập con có 2 phần tử: (3,1) là 2, (1,7) là 6, (7,2) là 5
-Các tập con có 3 phần tử: (3,1,7) là 6 , (1,7,2) là 6
-Các tập con có 4 phần tử là (3,1,7,2) là 6

Tổng là: 6+6+6+6+5+2=31.

Được gửi lên bởi:adm
Ngày:2013-07-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2024-07-04 13:45:42
#include <iostream>
#include <cmath>
int a[100000];
int dp[2][100000][21];
unsigned long long solve(int k, int f, int t) {
if (f > t) return 0;
int h = log2(t - f + 1);
int p;
if (k) {
p = (a[dp[k][f][h]] > a[dp[k][t - (1 << h) + 1][h]]) ? dp[k][f][h] : dp[k][t - (1 << h) + 1][h];
} else {
p = (a[dp[k][f][h]] < a[dp[k][t - (1 << h) + 1][h]]) ? dp[k][f][h] : dp[k][t - (1 << h) + 1][h];
}
unsigned long long res = 1ull * (p - f + 1) * (t - p + 1) * a[p];
res += solve(k, f, p - 1) + solve(k, p + 1, t);
return res;
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int n;
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
dp[0][i][0] = i;
dp[1][i][0] = i;
}
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
for (int k = 0; k < 2; ++k)
dp[k][i][j] = (a[dp[k][i][j - 1]] > a[dp[k][i + (1 << (j - 1))][j - 1]]) == k ? dp[k][i][j - 1] : dp[k][i + (1 << (j - 1))][j - 1];
std::cout << solve(1, 1, n) - solve(0, 1, n);
}
2022-03-16 18:02:40
bạn nào làm được bài này gửi cho mọi người đi
2019-08-15 19:02:45
40 :(
2019-07-11 10:54:41
Sinh =))
2018-07-26 16:57:50
def solved(arr,n):
new_arr = list.copy(arr)
lst = []
while new_arr != []:
i = 0
x = new_arr[i:n]
if len(x) == n:
lst.append(new_arr[i:n])
new_arr.remove(new_arr[i])
result = 0
for i in lst:
a = max(i) - min(i)
result += a
return result
if __name__ == '__main__':
x = int(input())
arr = []
for _ in range(x):
arr.append(int(input()))
kq = 0
for i in range(1,x+1):
kq += solved(arr,i)
print(kq)

mãi vẫn 20 :)
2017-12-10 17:37:11
bài này hay vãi :v mỗi tội mình không làm được
2017-05-24 05:11:42
làm mãi chỉ có 20 điểm :(
2015-08-18 17:53:48 62
giống bài đo chiều cao vãi :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.