Submission #990264

#	Time	Username	Problem	Language	Result	Execution time	Memory
990264		ian0704	Candies (JOI18_candies)	C++17	0 / 100	1 ms	600 KiB

candies

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf=1e16;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
ll arr[200010];
int n;
int ch[200010];
ll sum[200010];
int main()
{
    fastio;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    sum[1]=arr[1];
    for(int i=2;i<=n;i++) 
        sum[i]=sum[i-2]+arr[i];
    priority_queue<pair<ll,pair<ll,ll>>> pq_two;
    priority_queue<pair<ll,ll>> pq_one;
    set<pair<ll,ll>> s,s2;
    for(int i=1;i<=n;i++) pq_one.push({arr[i],i});
    ll res=0;
    for(int i=1;i<=n/2+n%2;i++)
    {
        pair<ll,ll> a={-inf,-inf};
        while(!pq_one.empty() && ch[pq_one.top().second]) pq_one.pop();
        if(!pq_one.empty()) a=pq_one.top();
        pair<ll,pair<ll,ll>> b={-inf,{-inf,-inf}};
        while(!pq_two.empty() && s2.count(pq_two.top().second)) pq_two.pop();
        if(!pq_two.empty()) b=pq_two.top();
        ll temp;
        //cout<<a.first<<" "<<a.second<<" | "<<b.first<<" "<<b.second.first<<" "<<b.second.second<<'\n';
        if(a.first>=b.first)
        {
            res+=a.first;
            ch[a.second]=1;
            ll l=a.second,r=a.second;
            if(l>1) l--;
            if(r<n) r++;
            auto idx=s.lower_bound({r,0});
            if(idx!=s.end())
            {
                //cout<<"-> "<<(*idx).first<<" "<<(*idx).second<<'\n';
                temp=(*idx).first;
                if(temp==r)
                {
                    r=(*idx).second;
                    s2.insert(*idx);
                    s.erase(idx);
                }                
            }
            if(idx!=s.begin())
                idx--;
            temp=(*idx).second;
            if(temp==l)
            {
                l=(*idx).first;
                s2.insert(*idx);
                s.erase(idx);
            }
            s.insert({l,r});
            ll num;
            if(r==n && r%2!=l%2)
            {
                num=sum[r-1]-sum[r];
                if(l>1) num+=sum[l-1]-sum[l-2];
            }
            else
            {
                num=sum[r]-sum[r-1];
                if(l>1) num+=sum[l-1]-sum[l-2];                
            }
            pq_two.push({num,{l,r}});
            ch[l]=1;
            ch[r]=1;
        }
        else
        {
            pq_two.pop();
            ll l=b.second.first,r=b.second.second;
            if(l>1) l--;
            if(r<n) r++;
            auto idx=s.lower_bound({r,0});
            if(idx!=s.end())
            {
                temp=(*idx).first;
                if(temp==r)
                {
                    r=(*idx).second;
                    s2.insert(*idx);
                    s.erase(idx);
                }                
            }
            if(idx!=s.begin())
                idx--;
            temp=(*idx).second;
            if(temp==l)
            {
                l=(*idx).first;
                s2.insert(*idx);
                s.erase(idx);
            }
            res+=b.first;
            s.insert({l,r});
            ll num;
            if(r==n && l%2!=r%2)
            {
                num=sum[r-1]-sum[r];
                if(l>1) num+=sum[l-1]-sum[l-2];
            }
            else
            {
                num=sum[r]-sum[r-1];
                if(l>1) num+=sum[l-1]-sum[l-2];
            }
            pq_two.push({num,{l,r}});
            ch[l]=1;
            ch[r]=1;
        }
        cout<<res<<'\n';
    }
}

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