Submission #1357805
Source Code Expand
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define boost() ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cout << fixed; cout << setprecision(15); srand(time(NULL))
#define ordered_set tree <pair <int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
#define endl '\n'
const int _n = 1e6 + 11;
const long long inf = (long long)1e18 + 1LL;
const long long mod = 1e9 + 7;
const long double eps = 1e-7;
int n, a[_n], st[_n * 4];
void build (int p, int l, int r) {
if (l == r) st[p] = l;
else {
build (2 * p, l, (l + r) / 2);
build (2 * p + 1, (l + r) / 2 + 1, r);
st[p] = ((a[st[2 * p]] < a[st[2 * p + 1]]) ? (st[2 * p]) : (st[2 * p + 1]));
}
}
int get (int p, int l, int r, int L, int R) {
if (l > r || l > R || r < L) return -1;
if (l >= L && r <= R) return st[p];
int v1 = get (2 * p, l, (l + r) / 2, L, R);
int v2 = get (2 * p + 1, (l + r) / 2 + 1, r, L, R);
if (v1 == -1 || v2 == -1) return max(v1, v2);
return ((a[v1] < a[v2]) ? (v1) : (v2));
}
int solve (int l, int r) {
if (l > r) return 0;
int v = get(1, 0, n - 1, l, r);
return (v - l + 1) * (r - v + 1) * a[v] + solve (l, v - 1) + solve (v + 1, r);
}
signed main () {
boost();
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
build (1, 0, n - 1);
cout << solve (0, n - 1) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
erdenebayr_d |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1610 Byte |
Status |
AC |
Exec Time |
86 ms |
Memory |
19840 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name |
Status |
Exec Time |
Memory |
corner0 |
AC |
54 ms |
10496 KB |
corner1 |
AC |
60 ms |
19840 KB |
corner2 |
AC |
2 ms |
2304 KB |
corner3 |
AC |
86 ms |
15232 KB |
example0 |
AC |
2 ms |
2304 KB |
example1 |
AC |
2 ms |
2304 KB |
example2 |
AC |
2 ms |
2304 KB |
maxrand0 |
AC |
65 ms |
10496 KB |
maxrand1 |
AC |
65 ms |
10496 KB |
maxrand2 |
AC |
64 ms |
10496 KB |
rand0 |
AC |
2 ms |
2304 KB |
rand1 |
AC |
2 ms |
2304 KB |
rand2 |
AC |
2 ms |
2304 KB |