#include <iostream>
#include <queue>
using namespace std;
#define endl '\n'
const int MAXN=2e5+10;
struct Node {
long long pl;
int l, r;
int idx;
bool friend operator < (Node a, Node b) {
return a.pl<b.pl;
}
};
priority_queue <Node> q;
int lef[MAXN], ri[MAXN], ind[MAXN], cnt;
long long a[MAXN], pref[MAXN];
bool used[2*MAXN];
long long find_sum(int l, int r) {
if (l==1) return pref[r];
return pref[r]-pref[l-2];
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i=1;i<=n;i++) {
cin >> a[i];
if (i==1) pref[i]=a[i];
else pref[i]=pref[i-2]+a[i];
lef[i]=ri[i]=i;
q.push({a[i],i,i,i});
}
long long sum=0;
cnt=n+1;
for (int i=1;i<=n/2+n%2;i++) {
while (used[q.top().idx]) q.pop();
auto p=q.top();
q.pop();
sum+=p.pl;
cout << sum << endl;
used[p.l-1]=used[p.r+1]=true;
if (p.l==1) {
used[ind[ri[p.r+1]]]=used[ind[p.r+1]]=true;
lef[ri[p.r+1]]=0;
continue;
}
if (p.r==n) {
used[ind[lef[p.l-1]]]=used[ind[p.l-1]]=true;
ri[lef[p.l-1]]=n+1;
continue;
}
int newl, newr;
newl=lef[p.l-1];
newr=ri[p.r+1];
ri[newl]=newr;
lef[newr]=newl;
used[ind[newl]]=used[ind[newr]]=used[p.idx]=true;
cnt++;
ind[newl]=ind[newr]=cnt;
long long ch=find_sum(newl,newr)-find_sum(newl+1,newr-1);
q.push({ch,newl,newr,cnt});
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
