Submission #1308047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308047		mpawicka_77	Candies (JOI18_candies)	C++20	100 / 100	147 ms	40008 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define int long long
set<pair<int,int>>S;
const int N=1e6+3, MAXN=(1<<20), INF=1e15;
int a[N], pref[N];
pair<int,int> D[2*MAXN+3];
int calc_kon(int ind)
{
    int kon=ind;
    auto it=S.lower_bound({ind, -1});
    if(it!=S.end()&&(*it).first<=ind+2)
    {
        auto x=*it;
        if(x.first==ind+1)
        {
            S.erase(it);
            x.first++, x.second++;
            kon=x.second;
            it=S.lower_bound({ind, -1});
            if(it!=S.end()&&(*it).first<=kon+2)
            {
                kon=(*it).second;
                S.erase(it);
            }
        }
        else
        {
            S.erase(it);
            kon=x.second;
        }
    }
    return kon;
}
int calc_pocz(int ind)
{
    int pocz=ind;
    auto it=S.lower_bound({ind, -1});
    if(it==S.begin())return pocz;
    it--;
    if((*it).second>=ind-2)
    {
        auto x=*it;
        if(x.second==ind-1)
        {
            S.erase(it);
            x.first--, x.second--;
            pocz=x.first;
            auto it=S.lower_bound({ind, -1});
            if(it==S.begin())return pocz;
            it--;
            if((*it).second>=pocz-2)
            {
                pocz=(*it).first;
                S.erase(it);
            }
        }
        else
        {
            S.erase(it);
            pocz=x.first;
        }
    }
    return pocz;
}
bool ok(int ind)
{
    auto it=S.lower_bound({ind+1, -1});
    if(it!=S.begin())
    {
        it--;
        if((*it).first<=ind&&(*it).second>=ind)return false;
    }
    return true;
}
void update(int x, int val)
{
    x+=MAXN;
    D[x].first=val;
    x/=2;
    while(x>0)
    {
        D[x]=max(D[2*x], D[2*x+1]);
        x/=2;
    }
}
int suma(int pocz, int kon)
{
    int s=pref[kon];
    if(pocz>=2)s-=pref[pocz-2];
    return s;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    a[0]=-INF, a[n+1]=-INF;

    for(int i=0; i<=n+1; i++)
    {
        pref[i]=a[i];
        if(i>=2)pref[i]+=pref[i-2];
    }
    for(int i=0; i<=2*MAXN; i++)D[i]= {-INF, i};
    for(int i=1; i<=n; i++)D[i+MAXN]= {a[i], i};
    for(int i=MAXN-1; i>=1; i--)D[i]=max(D[2*i], D[2*i+1]);

    int res=0;
    for(int i=1; i<=(n+1)/2; i++)
    {
        while(!ok(D[1].second))
        {
            update(D[1].second, -INF);
        }
        res+=D[1].first;
        cout<<res<<"\n";
        int ind=D[1].second;
        int pocz=calc_pocz(ind), kon=calc_kon(ind);
        S.insert({pocz, kon});

        if(pocz-1>0)update(pocz-1,suma(pocz-1, kon+1)-suma(pocz, kon));
        if(kon+1<=n)update(kon+1,suma(pocz-1, kon+1)-suma(pocz, kon));
    }
    return 0;
}

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