Submission #1590540
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)
template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}
typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;
const int inf = 1LL << 55;
const int mod = 1e9 + 7;
struct UnionFind {
vint data;
UnionFind(int n):data(n, -1){}
int find(int x) {
if(data[x] < 0) return x;
return data[x] = find(data[x]);
}
int size(int x) {
return -data[find(x)];
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(data[x] < data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
}
};
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cout << fixed << setprecision(12);
int N;
cin >> N;
vint a(N);
map<int, int> mp;
rep(i, N) {
cin >> a[i];
mp[a[i]] = i;
}
UnionFind uf(N);
int ans = 0;
for(int i = N; i >= 1; i--) {
int idx = mp[i];
ans += a[idx];
if(idx-1 >= 0 && a[idx] < a[idx-1]) {
ans += uf.size(idx)*uf.size(idx-1)*a[idx];
uf.unite(idx, idx-1);
}
if(idx+1 < N && a[idx] < a[idx+1]) {
ans += uf.size(idx)*uf.size(idx+1)*a[idx];
uf.unite(idx, idx+1);
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
ukuku09 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1653 Byte |
Status |
AC |
Exec Time |
138 ms |
Memory |
15872 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 |
138 ms |
15872 KB |
corner1 |
AC |
129 ms |
15872 KB |
corner2 |
AC |
1 ms |
256 KB |
corner3 |
AC |
114 ms |
15872 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
AC |
119 ms |
15872 KB |
maxrand1 |
AC |
117 ms |
15872 KB |
maxrand2 |
AC |
117 ms |
15872 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |