Submission #1051639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051639		noyancanturk	Candies (JOI18_candies)	C++17	100 / 100	158 ms	17524 KiB

candies

#include "bits/stdc++.h"
using namespace std;

#define int int64_t    
#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;
int mod=1e9+7;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n;
    cin>>n;
    int a[n],b[n],ll[n]{},rr[n]{};
    for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}
    priority_queue<pii>pq;
    for(int i=0;i<n;i++){
        pq.push({a[i],i});
    }
    int cnt=0;
    int pref[n];
    pref[0]=a[0];
    if(n)pref[1]=a[1];
    for(int i=2;i<n;i++){
        pref[i]=pref[i-2]+a[i];
    }
    auto f=[&](int l,int r){
        return pref[r]-(1<l?pref[l-2]:int(0));
    };
    set<pii>st;
    int ans=0;
    for(int i=1;i<=(n+1)/2;i++){
        while(pq.size()){
            auto[val,ind]=pq.top();
            pq.pop();
            if(val!=b[ind])continue;
            auto p=st.lower_bound({ind,ind}),q=(p==st.begin())?st.end():prev(p);
            int l=ind,r=ind;
            if(q!=st.end()){
                if(q->first<=ind&&ind<=q->second)continue;
                if(!q->first&&ind-1==q->second)continue;
            }
            if(p!=st.end()){
                if(p->first<=ind&&ind<=p->second)continue;
            }
            //cerr<<val<<" "<<ind<<"\n";
            if(p!=st.end()&&p->first<=ind+2){
                if(p->first==ind+1&&p->second==n-1)continue;
                r=p->second;
                st.erase(p);
            }
            if(q!=st.end()&&ind-2<=q->second){
                //cerr<<q->first<<" "<<q->second<<"\n";
                l=q->first;
                st.erase(q);
            }
            //cerr<<l<<" "<<r<<" lr\n";
            if((r&1)!=(ind&1)){
                r++;
                if(n<=r)r-=2;
            }
            if((l&1)!=(ind&1)){
                l--;
                if(l<0)l-=2;
            }
            p=st.lower_bound({r,0});
            while(p!=st.end()&&p->first==r+2){
                r=p->second;
                st.erase(p);
                p=st.lower_bound({r,0});
            }
            p=st.lower_bound({r,0});
            while(p!=st.begin()&&(--p)->second==l-2){
                l=p->first;
                st.erase(p);
                p=st.lower_bound({r,0});
            }
            //cerr<<ind<<" "<<val<<" using \n";
            ans+=val;
            //cerr<<l<<" "<<r<<" lr\n";
            st.insert({l,r});
            if(l&&r+1<n){
                int k=f(l,r)-((l+1<n)?f(l+1,r+1<n?r+1:r-1):0);
                ll[l-1]=k;
                b[l-1]=a[l-1]-ll[l-1]-rr[l-1];
                pq.push({b[l-1],l-1});
                k=f(l,r)-((0<=r-1)?f(0<=l-1?l-1:l+1,r-1):0);
                rr[r+1]=k;
                b[r+1]=a[r+1]-ll[r+1]-rr[r+1];
                pq.push({b[r+1],r+1});
            }
            break;
        }
        cout<<ans<<"\n";
        /*
        for(int i:b){
            cerr<<i<<" ";
        }cerr<<"\n";
        cerr<<"ranges:\n";
        for(auto[f,s]:st){
            cerr<<f<<" "<<s<<"\n";
        }cerr<<"\n";
        */
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:25:9: warning: unused variable 'cnt' [-Wunused-variable]
   25 |     int cnt=0;
      |         ^~~

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