#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define f first
#define s second
const int N = 200005;
int n, arr[N], psum[N];
set<pii> se; ll ans;
priority_queue<pair<pli, pii>> pq;
ll sum(pii x){
return psum[x.s]-(x.f>=2?psum[x.f-2]:0);
}
int main(){
// freopen("a.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 0; i<n; ++i)
cin >> arr[i];
for(int i = 0; i<n; ++i)
psum[i] = arr[i]+(i>=2?psum[i-2]:0);
for(int i = 0; i<n; ++i)
pq.push({{(ll)arr[i], 1}, {i, i-2}});
for(int i = 1; i<=(n+1)/2;){
auto tmp = pq.top(); pq.pop();
ll gain = tmp.f.f;
int type = tmp.f.s;
int l = tmp.s.f, r = tmp.s.s;
if(r!=l-2 && !se.count({l, r})) continue;
int nl, nr;
if(r==l-2){
auto it = se.lower_bound({l, r});
if((it!=se.end() && it->f<=l+2) || (it!=se.begin() && prev(it)->s>=l-2))
continue;
nl = nr = l;
} else if(type==0){
auto it = se.lower_bound({l, r});
if(it!=se.begin() && prev(it)->s==l-3)
continue;
if(it!=se.begin() && prev(it)->s==l-4){
nl = prev(it)->f, nr = r;
se.erase(prev(it));
se.erase({l, r});
} else{
nl = l-2, nr = r;
se.erase({l, r});
}
} else if(type==1){
auto it = se.upper_bound({l, r});
if(it!=se.end() && it->f==r+3)
continue;
if(it!=se.end() && it->f==r+4){
nl = l, nr = it->s;
se.erase(it);
se.erase({l, r});
} else{
nl = l, nr = r+2;
se.erase({l, r});
}
} else{
auto it = se.lower_bound({l, r});
pii p1 = {-1, -1}, p2 = {-1, -1};
if(next(it)!=se.end() && next(it)->f==r+3)
nr = next(it)->s, p2 = *next(it);
else nr = r+1;
if(it!=se.begin() && prev(it)->s==l-3)
nl = prev(it)->f, p1 = *prev(it);
else nl = l-1;
se.erase({l, r});
if(p1.f!=-1) se.erase(p1);
if(p2.f!=-1) se.erase(p2);
}
ans += gain;
se.insert({nl, nr});
auto it = se.lower_bound({nl, nr});
if(nl>=2 && (it==se.begin() || prev(it)->s!=nl-3))
pq.push({{arr[nl-2], 0}, {nl, nr}});
if(nr<=n-1-2 && (next(it)==se.end() || next(it)->f!=nr+3))
pq.push({{arr[nr+2], 1}, {nl, nr}});
if(nl>=1 && nr<=n-1-1)
pq.push({{sum({nl-1, nr+1})-sum({nl, nr}), 2}, {nl, nr}});
cout << ans << '\n'; ++i;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
