//Billions of bilious blue blistering barnacles in a thundering typhoon!
//Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present.
#include<bits/stdc++.h>
#define F first
#define S second
#define lx node * 2
#define rx node * 2 + 1
#define md ((s + e) / 2)
#define mid ((l + r) / 2)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
ll pref[200005];
int a[200005], L[200005], R[200005], n;
set < pair < int, int > > se;
set < pair < ll, pair < int, int > > > Se;
void add(int l, int r){
Se.insert({(r == n ? pref[r - 1] : pref[r + 1]) - (l <= 2 ? 0 : pref[l - 3]) - ((pref[r] - (l <= 2 ? 0 : pref[l - 2]))), {l, r}});
}
void remove(int l, int r){
Se.erase({(r == n ? pref[r - 1] : pref[r + 1]) - (l <= 2 ? 0 : pref[l - 3]) - ((pref[r] - (l <= 2 ? 0 : pref[l - 2]))), {l, r}});
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
se.insert({a[i], i});
pref[i] = (i > 1 ? pref[i - 2] : 0) + a[i];
}
ll ans = 0;
for(int i = 1; i <= (n + 1) / 2; i++){
ll val1 = (se.empty() ? (ll)-1e18 : (*se.rbegin()).F);
ll val2 = (Se.empty() ? (ll)-1e18 : (*Se.rbegin()).F);
if(val1 > val2){
ans += val1;
int j = (*se.rbegin()).S;
se.erase({a[j], j});
se.erase({a[j - 1], j - 1});
se.erase({a[j + 1], j + 1});
int l = j, r = j;
if(j > 2 && L[j - 2]){
remove(L[j - 2], j - 2);
l = L[j - 2];
}
if(j < n - 1 && R[j + 2]){
remove(j + 2, R[j + 2]);
r = R[j + 2];
}
L[r] = l, R[l] = r;
add(l, r);
}
else{
ans += val2;
auto [l, r] = (*Se.rbegin()).S;
remove(l, r);
if(l == 1)l++;
else l--;
if(r == n)r--;
else r++;
if(l > 2 && L[l - 2]){
remove(L[l - 2], l - 2);
l = L[l - 2];
}
if(r < n - 1 && R[r + 2]){
remove(r + 2, R[r + 2]);
r = R[r + 2];
}
L[r] = l, R[l] = r;
se.erase({a[l - 1], l - 1});
se.erase({a[r + 1], r + 1});
add(l, r);
}
cout << ans << "\n";
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
