Submission #58242

#	Time	Username	Problem	Language	Result	Execution time	Memory
58242		alenam0161	Candies (JOI18_candies)	C++17	0 / 100	6 ms	504 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 fnd(int v){
    return v==p[v] ? v:p[v]=fnd(p[v]);
}
int main(){
   // freopen("input.txt","r",stdin);
    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];
    }
    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;
    while(st.size()>0){
        auto it=st.end();it--;
        long long vl=it->first;
        int ps=it->second;
        ps=fnd(ps);
        ans+=vl;
        hw--;
        if(hw<0){
            return 0;
        }
        cout<<ans<<endl;
        if(l[ps]==1&&r[ps]==n){
            return 0;
        }
        st.erase(st.find({vl,ps}));
        val[ps]*=-1;
        if(l[ps]>1){
            int pl=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){
            int pr=r[ps]+1;
            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:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
candies.cpp:14: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: 0 / 8
• Subtask 2: 0 / 92