Submission #673355

#	Time	Username	Problem	Language	Result	Execution time	Memory
673355		Hanksburger	Candies (JOI18_candies)	C++17	100 / 100	421 ms	19500 KiB

candies

#include <bits/stdc++.h>
#define ll long long
using namespace std;
set<pair<ll, pair<ll, ll> > > q;
ll a[200005], b[200005];
set<pair<ll, ll> > s;
ll f(ll l, ll r)
{
    return b[r]-b[l-2]-b[r+1]+(l<3?0:b[l-3]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, k=0;
    cin >> n;
    for (ll i=1; i<=n; i++)
    {
        cin >> a[i];
        b[i]=(i<2?0:b[i-2])+a[i];
        q.insert({-a[i], {i, i}});
    }
    for (ll i=1; i<=(n+1)/2; i++)
    {
        cout << (k-=(*q.begin()).first) << '\n';
        ll l=(*q.begin()).second.first, r=(*q.begin()).second.second;
        if (l<r)
            s.erase({l+1, r-1});
        q.erase(q.begin());
        q.erase({-a[l-1], {l-1, l-1}});
        q.erase({-a[r+1], {r+1, r+1}});
        auto it=s.lower_bound({l, r});
        if (it!=s.begin() && (*prev(it)).second==l-2)
        {
            ll L=(*prev(it)).first, R=(*prev(it)).second;
            s.erase({L, R});
            s.erase({l, r});
            if (L>1 && R<n)
                q.erase({f(L, R), {L-1, R+1}});
            l=L;
        }
        if (it!=s.end() && (*it).first==r+2)
        {
            ll L=(*it).first, R=(*it).second;
            s.erase({L, R});
            s.erase({l, r});
            if (L>1 && R<n)
                q.erase({f(L, R), {L-1, R+1}});
            r=R;
        }
        s.insert({l, r});
        if (l>1 && r<n)
            q.insert({f(l, r), {l-1, r+1}});
    }
}

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