Submission #932075

#	Time	Username	Problem	Language	Result	Execution time	Memory
932075		mdn2002	Candies (JOI18_candies)	C++14	100 / 100	417 ms	26088 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;
    a [0] = a [ n + 1 ] = -1e15;
    sum [0][0] = a [0];
    for ( int i = 0 ; i <= n + 1 ; i ++ )
    {
        if ( 1 <= i && i <= n ) 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;
        //cout << ' ' << l [lx] << ' ' << lx << "   " << rx << ' ' << r [rx] << ' ' << x . second . first << ' ' << x . second . second << ' ' << x . first << ' ' << sum << endl;
        ss . erase ( ss . lower_bound ( { cost ( rx , r [rx] ) , { rx , r [rx] } } ) );
        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

10
5383 5238 56 6356 64359 6235 23487 6693 3552 23443
64359
87846
111289
116672
116728
*/

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