#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[y] = min(lt[x], lt[y]);
rt[y] = 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) {
st.erase(make_pair(uf.inc[ltcomp], ltcomp));
}
//erase right
if (rtcomp != N + 1) {
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]);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3684 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3684 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3684 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
8 ms |
3796 KB |
Output is correct |
| 7 |
Correct |
8 ms |
3796 KB |
Output is correct |
| 8 |
Correct |
9 ms |
3872 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3904 KB |
Output is correct |
| 10 |
Correct |
8 ms |
3904 KB |
Output is correct |
| 11 |
Correct |
9 ms |
3904 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3904 KB |
Output is correct |
| 13 |
Correct |
9 ms |
3920 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4080 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4180 KB |
Output is correct |
| 16 |
Correct |
8 ms |
4180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
4248 KB |
Output is correct |
| 18 |
Correct |
9 ms |
4248 KB |
Output is correct |
| 19 |
Correct |
7 ms |
4248 KB |
Output is correct |
| 20 |
Correct |
8 ms |
4248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3684 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3684 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3684 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3796 KB |
Output is correct |
| 6 |
Correct |
8 ms |
3796 KB |
Output is correct |
| 7 |
Correct |
8 ms |
3796 KB |
Output is correct |
| 8 |
Correct |
9 ms |
3872 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3904 KB |
Output is correct |
| 10 |
Correct |
8 ms |
3904 KB |
Output is correct |
| 11 |
Correct |
9 ms |
3904 KB |
Output is correct |
| 12 |
Correct |
7 ms |
3904 KB |
Output is correct |
| 13 |
Correct |
9 ms |
3920 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4080 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4180 KB |
Output is correct |
| 16 |
Correct |
8 ms |
4180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
4248 KB |
Output is correct |
| 18 |
Correct |
9 ms |
4248 KB |
Output is correct |
| 19 |
Correct |
7 ms |
4248 KB |
Output is correct |
| 20 |
Correct |
8 ms |
4248 KB |
Output is correct |
| 21 |
Correct |
689 ms |
23140 KB |
Output is correct |
| 22 |
Correct |
726 ms |
25188 KB |
Output is correct |
| 23 |
Correct |
655 ms |
26884 KB |
Output is correct |
| 24 |
Correct |
267 ms |
26896 KB |
Output is correct |
| 25 |
Correct |
257 ms |
27000 KB |
Output is correct |
| 26 |
Correct |
240 ms |
27000 KB |
Output is correct |
| 27 |
Correct |
237 ms |
27000 KB |
Output is correct |
| 28 |
Correct |
216 ms |
27000 KB |
Output is correct |
| 29 |
Correct |
261 ms |
27000 KB |
Output is correct |
| 30 |
Correct |
227 ms |
27000 KB |
Output is correct |
| 31 |
Correct |
227 ms |
27000 KB |
Output is correct |
| 32 |
Correct |
316 ms |
27000 KB |
Output is correct |
| 33 |
Correct |
440 ms |
27000 KB |
Output is correct |
| 34 |
Correct |
442 ms |
27036 KB |
Output is correct |
| 35 |
Correct |
439 ms |
27036 KB |
Output is correct |
| 36 |
Correct |
750 ms |
27056 KB |
Output is correct |
| 37 |
Correct |
597 ms |
27056 KB |
Output is correct |
| 38 |
Correct |
689 ms |
27056 KB |
Output is correct |
| 39 |
Correct |
235 ms |
27056 KB |
Output is correct |
| 40 |
Correct |
274 ms |
27056 KB |
Output is correct |
| 41 |
Correct |
284 ms |
27056 KB |
Output is correct |
| 42 |
Correct |
249 ms |
27056 KB |
Output is correct |
| 43 |
Correct |
234 ms |
27056 KB |
Output is correct |
| 44 |
Correct |
219 ms |
27056 KB |
Output is correct |
| 45 |
Correct |
292 ms |
27056 KB |
Output is correct |
| 46 |
Correct |
354 ms |
27056 KB |
Output is correct |
| 47 |
Correct |
289 ms |
27056 KB |
Output is correct |
| 48 |
Correct |
437 ms |
27056 KB |
Output is correct |
| 49 |
Correct |
434 ms |
27056 KB |
Output is correct |
| 50 |
Correct |
442 ms |
27056 KB |
Output is correct |
