Submission #934437

#	Time	Username	Problem	Language	Result	Execution time	Memory
934437		alexander707070	Candies (JOI18_candies)	C++14	100 / 100	287 ms	30924 KiB

candies

#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

const long long inf=1e17;

struct node{
    int l,r;
    int from,to;
    long long res;
};

int n,best;
long long a[MAXN],sum,maxs,curr;
bool used[MAXN];

long long even[MAXN],odd[MAXN];
node w[MAXN];

void erasev(int x){
    w[w[x].l].r=w[x].r;
    w[w[x].r].l=w[x].l;
}

long long pref[MAXN];

long long summ(int l,int r){
    if(l%2==0){
        return pref[r]-pref[l-2];
    }else{
        if(l==1)return pref[r];
        else return pref[r]-pref[l-2];
    }
}

set< pair<long long,int> > s;
pair<long long,int> z;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=a[i];
        w[i]={i-1,i+1,i,i,a[i]};

        s.insert({w[i].res,i});
    }

    for(int i=2;i<=n;i++){
        pref[i]+=pref[i-2];
    }

    w[0].r=1;
    w[n+1].l=n;

    for(int i=1;i<=n/2+n%2;i++){
        z=*s.rbegin();

        maxs=z.first;
        best=z.second;

        s.erase(z);

        sum+=maxs;

        if(w[best].l==0){
            s.erase({w[w[best].r].res,w[best].r});
            erasev(w[best].r);
            erasev(best);

        }else if(w[best].r==n+1){
            s.erase({w[w[best].l].res,w[best].l});
            erasev(w[best].l);
            erasev(best);
        }else{
            w[best].from=w[w[best].l].from;
            w[best].to=w[w[best].r].to;

            w[best].res=summ(w[best].from,w[best].to)-summ(w[best].from+1,w[best].to-1);

            s.erase({w[w[best].l].res,w[best].l});
            erasev(w[best].l);

            s.erase({w[w[best].r].res,w[best].r});
            erasev(w[best].r);

            s.insert({w[best].res,best});
        }
        
        cout<<sum<<"\n";
    }

    return 0;
}

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