#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
struct union_find {
int par[MAXN];
int sz[MAXN];
int lt[MAXN];
int rt[MAXN];
ll inc[MAXN];
union_find() {
for (int i = 0; i < MAXN; i++) {
par[i] = i;
sz[i] = 1;
lt[i] = i;
rt[i] = i;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void merge (int x, int y) {
x = find(x);
y = find(y);
assert(x != y);
par[x] = y;
sz[y] += sz[x];
lt[x] = min(lt[x], lt[y]);
rt[x] = max(rt[x], rt[y]);
}
};
int N;
ll A[MAXN];
union_find uf = union_find();
set<pair<ll, int>> st;
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%lld", &A[i]);
uf.inc[i] = A[i];
st.insert(make_pair(uf.inc[i], i));
}
ll ans = 0;
for (int i = 1; ; i++) {
auto p = *st.rbegin();
st.erase(--st.end());
int ccomp = uf.find(p.se);
ans += p.fi;
printf("%lld\n", ans);
if (i == (N + 1) / 2) {
break;
}
int ltcomp = uf.find(uf.lt[ccomp] - 1);
int rtcomp = uf.find(uf.rt[ccomp] + 1);
ll ninc = uf.inc[ltcomp] + uf.inc[rtcomp] - uf.inc[ccomp];
//erase left
if (ltcomp != 0) {
assert(st.erase(make_pair(uf.inc[ltcomp], ltcomp)));
}
//erase right
if (rtcomp != N + 1) {
assert(st.erase(make_pair(uf.inc[rtcomp], rtcomp)));
}
//ok unite the sides - left & right.
//EVEN IF THE LEFT IS THE ZERO. THIS WAY YOU WILL NEVER SELECT THIS AGAIN.
uf.merge(ltcomp, ccomp);
uf.merge(ccomp, rtcomp);
ccomp = uf.find(ccomp);
if (uf.lt[ccomp] != 0 && uf.rt[ccomp] != N + 1) {
uf.inc[ccomp] = ninc;
st.insert(make_pair(ninc, ccomp));
}
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
candies.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &A[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
7108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
7108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
