Submission #619663

#	Time	Username	Problem	Language	Result	Execution time	Memory
619663		chonka	Candies (JOI18_candies)	C++17	100 / 100	120 ms	10808 KiB

candies

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 2e5 + 7 ;
const ll inf = 1e18 ;

int n ;
ll a[ MAXN ] ;

int prv[ MAXN ] ;
ll sm[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] ;
bool done[ MAXN ] ;

priority_queue < pair < ll , int > > q ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

void unite ( int x , int y ) {
    int k1 = get ( x ) ;
    int k2 = get ( y ) ;
    if ( k1 != k2 ) {
        done[ k2 ] = true ;
        sm[ k1 ] += sm[ k2 ] ;
        prv[ k2 ] = k1 ;
        st[ k1 ] = min ( st[ k1 ] , st[ k2 ] ) ;
        en[ k1 ] = max ( en[ k1 ] , en[ k2 ] ) ;
    }
}

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }

    a[ 0 ] = a[ n + 1 ] = -inf ;
    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        prv[ i ] = -1 , sm[ i ] = a[ i ] ;
        en[ i ] = st[ i ] = i ;
        if ( 1 <= i && i <= n ) { 
            q.push ( { sm[ i ] , i } ) ;
        }
    }

    ll ans = 0 ;
    for ( int i = 1 ; i <= ( n + 1 ) / 2 ; ++ i ) {
        while ( q.empty ( ) == false ) { 
            auto [ aux , wh ] = q.top ( ) ;
            q.pop ( ) ;
            if ( done[ wh ] == true ) { continue ; }
            ans += aux ;
            cout << ans << "\n" ;
            sm[ wh ] = -sm[ wh ] ;
            done[ get ( st[ wh ] - 1 ) ] = done[ get ( en[ wh ] + 1 ) ] = true ;
            unite ( wh , st[ wh ] - 1 ) ;
            unite ( wh , en[ wh ] + 1 ) ;
            q.push ( { sm[ wh ] , wh } ) ;
            break ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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