oj.uz

Submission #58262

# Submission time Handle Problem Language Result Execution time Memory
58262 2018-07-17T10:13:51 Z alenam0161 Candies (JOI18_candies) C++17
0 / 100
 10 ms 1276 KB 
#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;
    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(hw==0)return 0;
        if(l[ps]==1&&r[ps]==n){
            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]!=n){
                int pxl=r[pl]-1;pxl=fnd(pxl);
                p[pl]=p[pxl];
                r[pxl]=l[pl];
            }
            else {
                val[pl]*=-1;
                val[pl]+=val[ps];
                st.insert({val[pl],pl});
            }
        }
        else{
            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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Runtime error 10 ms 1276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Runtime error 10 ms 1276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -