#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;
const ll INF = 1e16;
int N;
ll A[MAXN+10], ans;
set<int> L, R;
set<pll, greater<pll>> S;
pii f(int x)
{
int l, r;
r=*R.lower_bound(x);
l=*(--L.upper_bound(x));
return {l, r};
}
int main()
{
int i, j;
scanf("%d", &N);
for(i=1; i<=N; i++) scanf("%lld", &A[i]);
for(i=0; i<=N+1; i++) L.insert(i), R.insert(i);
for(i=1; i<=N; i++) S.insert({A[i], i});
for(i=1; i<=(N+1)/2; i++)
{
ans+=S.begin()->first;
printf("%lld\n", ans);
int x=S.begin()->second;
int l=f(x).first, r=f(x).second, pl=f(l-1).first, pr=f(l-1).second, ql=f(r+1).first, qr=f(r+1).second;
assert(A[l]==S.begin()->first);
L.erase(l), R.erase(r), S.erase({A[l], l});
if(l!=1) L.erase(pl), R.erase(pr), S.erase({A[pl], pl});
if(r!=N) L.erase(ql), R.erase(qr), S.erase({A[ql], ql});
if(l!=1 && r!=N)
{
A[pl]=A[pl]+A[ql]-A[l];
L.insert(pl); R.insert(qr); S.insert({A[pl], pl});
}
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:27:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
candies.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
candies.cpp:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%lld", &A[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
