#include<bits/stdc++.h>
using namespace std;
//#include"nuts.h"
#define ll long long
#define x first
#define y second
#define pi pair<ll,ll>
vector<long long> Nuts(int n, vector<int> v){
priority_queue<pi> pq;
ll l[n],r[n];
for(ll i=0;i<n;i++){
pq.push({v[i],i});
l[i]=i-1;r[i]=i+1;
}
vector<bool> vis(n,0);
ll res=0;
vector<ll> ans;
for(ll i=0; i< (n+1)/2;i++){
while(vis[pq.top().y]) pq.pop();
pi p = pq.top(); pq.pop();
res += p.x;
ans.push_back(res);
ll cur = p.y;
if(r[cur]==n){
vis[cur]=1;
if(l[cur]!=-1)vis[l[cur]]=1;
if(l[l[cur]] > -1) r[l[l[cur]]]=n;
}
else if(l[cur]==-1){
vis[cur]=1;
if(r[cur]!=n)vis[r[cur]]=1;
if(r[r[cur]] < n) l[r[r[cur]]]=-1;
}
else{
v[cur] = v[r[cur]]+v[l[cur]] - v[cur];
vis[r[cur]]=1;
r[cur] = r[r[cur]];
if(r[cur] != n) l[r[cur]]=cur;
vis[l[cur]]=1;
l[cur] = l[l[cur]];
if(l[cur] != -1) r[l[cur]]=cur;
pq.push({v[cur],cur});
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<int> nuts(n);
for(int i=0;i<n;i++) cin>>nuts[i];
vector<long long> ans = Nuts(n, nuts);
for(long long c : ans) cout<<c<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
