Submission #58269

#	Time	Username	Problem	Language	Result	Execution time	Memory
58269		alenam0161	Candies (JOI18_candies)	C++17	100 / 100	737 ms	46480 KiB

candies

#include <bits/stdc++.h>
using namespace std;
const int N = 200000+7;
int a[N];
int l[N],r[N],p[N];
long long val[N];
int sz[N];
int fnd(int v){
    return v==p[v] ? v:p[v]=fnd(p[v]);
}
int main(){

    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        r[i]=l[i]=p[i]=i;
        val[i]=a[i];
        sz[i]=1;
    }
    multiset<pair<long long,int> > st;
    for(int i=1;i<=n;++i){
        st.insert({a[i],i});
    }
    int hw=(n+1)/2;
    long long ans=0;
    p[n+1]=n+1;
    p[0]=0;
    while(st.size()>0){
        auto it=st.end();it--;
        long long vl=it->first;
        int ps=it->second;
        ps=fnd(ps);
        ans+=vl;
        hw--;
        cout<<ans<<endl;
        if(hw==0)return 0;
        st.erase(st.find({vl,ps}));
        val[ps]*=-1;
        int pl=l[ps]-1;pl=fnd(pl);
        int pr=r[ps]+1;pr=fnd(pr);
        if(l[ps]==1){
            p[ps]=pr;
            l[pr]=l[ps];
            st.erase(st.find({val[pr],pr}));
            if(r[pr]<n){
                int pxr=r[pr]+1;pxr=fnd(pxr);
                p[pr]=p[pxr];
                l[pxr]=l[pr];
            }
            else {
                val[pr]*=-1;
                val[pr]+=val[ps];
                st.insert({val[pr],pr});
            }
        }
        else if(r[ps]==n){
            p[ps]=pl;
            r[pl]=r[ps];
            st.erase(st.find({val[pl],pl}));
            if(l[pl]!=1){
                int pxl=l[pl]-1;pxl=fnd(pxl);
                p[pl]=p[pxl];
                r[pxl]=r[pl];
            }
            else {
                val[pl]*=-1;
                val[pl]+=val[ps];
                st.insert({val[pl],pl});
            }
        }
        else{
            if(l[ps]>1){
                pl=fnd(pl);
                val[ps]+=val[pl];
                l[ps]=l[pl];
                p[pl]=ps;
                st.erase(st.find({val[pl],pl}));
            }
            if(r[ps]<n){
                pr=fnd(pr);
                val[ps]+=val[pr];
                r[ps]=r[pr];
                p[pr]=ps;
                st.erase(st.find({val[pr],pr}));
            }
            st.insert({val[ps],ps});
        }
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
candies.cpp:15:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;++i)scanf("%d",&a[i]);
                          ~~~~~^~~~~~~~~~~~

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