#include <bits/stdc++.h>
using namespace std;
int const NMAX=200005;
int lp[NMAX],rp[NMAX];
long long val[NMAX];
set<pair<long long,int>>upd;
int n;
void read(){
cin>>n;
int i;
lp[0]=0;
rp[0]=1;
lp[n+1]=n;
rp[n+1]=n+1;
for(i=1;i<=n;++i){
int value;
cin>>value;
lp[i]=i-1;
rp[i]=i+1;
val[i]=value;
upd.insert({value,i});
}
}
void solve(){
long long sum=0;
while(!upd.empty()){
auto [add,id]=*upd.rbegin();
sum+=add;
cout<<sum<<'\n';
int id1=lp[id];
int id2=id;
int id3=rp[id];
upd.erase({add,id});
if(id1>0)
upd.erase({val[id1],id1});
if(id3<=n)
upd.erase({val[id3],id3});
if(0<id1 && id3<=n){
rp[id1]=rp[id3];
lp[rp[id3]]=id1;
val[id1]+=val[id3]-val[id2];
upd.insert({val[id1],id1});
}
else
if(0<id1){
rp[lp[id1]]=n+1;
lp[n+1]=lp[id1];
}
else
if(id3<=n){
lp[rp[id3]]=0;
rp[0]=rp[id3];
}
else{
rp[0]=n+1;
lp[n+1]=0;
}
}
}
int main()
{
read();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |