/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 1000000;
int N;
int A[N_MAX + 2];
int cost[N_MAX + 2];
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
set <int> s; s.insert(INT_MAX);
for (int i = 1; i <= N; i++) {
cost[i] += *s.upper_bound(A[i]);
s.insert(A[i]);
}
s.clear(); s.insert(INT_MAX);
for (int i = N; i >= 1; i--) {
cost[i] += *s.upper_bound(A[i]);
s.insert(A[i]);
}
ll answer = 0;
for (int i = 2; i <= N - 1; i++) {
int mn = min(A[i - 1], A[i + 1]);
if (A[i] < mn) {
answer += (ll) cost[i] * (mn - A[i]);
answer += (ll) mn * (mn - 1) / 2 - (ll) A[i] * (A[i] - 1) / 2;
}
}
cout << answer << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |