Submission #618128

#	Time	Username	Problem	Language	Result	Execution time	Memory
618128		chonka	Candies (JOI18_candies)	C++17	0 / 100	1 ms	468 KiB

candies

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

const int MAXN = 2e5 + 7 ;

int n ;
int a[ MAXN ] ;

int prv[ MAXN ] ;
ll sm[ MAXN ] ;
int st[ MAXN ] , en[ 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 ) {
        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 ] ;
        prv[ i ] = -1 , sm[ i ] = a[ i ] ;
        en[ i ] = st[ i ] = i ;

        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 ( wh != get ( wh ) ) { continue ; }
            ans += aux ;
            cout << ans << "\n" ;
            sm[ wh ] = -sm[ wh ] ;
            if ( st[ wh ] != 1 ) {
                unite ( wh , st[ wh ] - 1 ) ;
            }
            if ( en[ wh ] != n ) {
                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: 0 / 8
• Subtask 2: 0 / 92