Submission #517161

#	Time	Username	Problem	Language	Result	Execution time	Memory
517161		couplefire	Candies (JOI18_candies)	C++17	0 / 100	2 ms	464 KiB

candies

#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;
    }
}

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