Submission #932983

#	Time	Username	Problem	Language	Result	Execution time	Memory
932983		Blistering_Barnacles	Candies (JOI18_candies)	C++17	100 / 100	263 ms	17256 KiB

candies

//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){
    if(l == 1 || r == n)return;
    Se.insert({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){
    if(l == 1 || r == n)return;
    Se.erase({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(); 
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92