Submission #932068

#	Time	Username	Problem	Language	Result	Execution time	Memory
932068		mdn2002	Candies (JOI18_candies)	C++14	0 / 100	3 ms	4700 KiB

candies

/*
    Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>

using namespace std;

long long n , a [200005] , sum [200005][3] , l [200005] , r [200005];
set < pair < long long , pair < int , int > > > ss;

long long cost ( int l , int r )
{
    long long ans = sum [r][ r % 2 ] - sum [ l - 1 ][ r % 2 ];
    ans -= sum [ r - 1 ][ ( r - 1 ) % 2 ] - sum [l][ ( r - 1 ) % 2 ];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for ( int i = 1 ; i <= n ; i ++ )
    {
        cin >> a [i];
        sum [i][0] = sum [ i - 1 ][0];
        sum [i][1] = sum [ i - 1 ][1];
        sum [i][ i % 2 ] += a [i];
        l [i] = r [i] = i;
        ss . insert ( { a [i] , { i , i } } );
    }

    long long num = ( n + 1 ) / 2 , sum = 0;
    for ( int i = 1 ; i <= num ; i ++ )
    {
        auto x = * -- ss . end ();
        ss . erase ( -- ss . end () );
        sum += x . first;
        int lx = x . second . first - 1 , rx = x . second . second + 1;
        if ( rx <= n ) ss . erase ( ss . lower_bound ( { cost ( rx , r [rx] ) , { rx , r [rx] } } ) );
        if ( lx >= 1 ) ss . erase ( ss . lower_bound ( { cost ( l [lx] , lx ) , { l [lx] , lx } } ) );
        lx = l [lx] , rx = r [rx];
        r [lx] = rx , l [rx] = lx;
        ss . insert ( { cost ( lx , rx ) , { lx , rx } } );
        cout << sum << endl;
    }
}
/*
5
3 5 1 7 6
*/

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