Submission #1222874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222874		AlgorithmWarrior	Candies (JOI18_candies)	C++20	100 / 100	216 ms	18020 KiB

candies

#include <bits/stdc++.h>

using namespace std;

int const NMAX=200005;
int lp[NMAX],rp[NMAX];
long long val[NMAX];
set<pair<long long,int>>upd;
int n;

void read(){
    cin>>n;
    int i;
    lp[0]=0;
    rp[0]=1;
    lp[n+1]=n;
    rp[n+1]=n+1;
    for(i=1;i<=n;++i){
        int value;
        cin>>value;
        lp[i]=i-1;
        rp[i]=i+1;
        val[i]=value;
        upd.insert({value,i});
    }
}

void solve(){
    long long sum=0;
    while(!upd.empty()){
        auto [add,id]=*upd.rbegin();
        sum+=add;
        cout<<sum<<'\n';
        int id1=lp[id];
        int id2=id;
        int id3=rp[id];
        upd.erase({add,id});
        if(id1>0)
            upd.erase({val[id1],id1});
        if(id3<=n)
            upd.erase({val[id3],id3});
        if(0<id1 && id3<=n){
            rp[id1]=rp[id3];
            lp[rp[id3]]=id1;
            val[id1]+=val[id3]-val[id2];
            upd.insert({val[id1],id1});
        }
        else
        if(0<id1){
            rp[lp[id1]]=n+1;
            lp[n+1]=lp[id1];
        }
        else
        if(id3<=n){
            lp[rp[id3]]=0;
            rp[0]=rp[id3];
        }
        else{
            rp[0]=n+1;
            lp[n+1]=0;
        }
    }
}

int main()
{
    read();
    solve();
    return 0;
}

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