Submission #543032

#	Time	Username	Problem	Language	Result	Execution time	Memory
543032		chonka	Constellation 3 (JOI20_constellation3)	C++98	100 / 100	451 ms	38280 KiB

constellation3

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

#define MAXN 200007

int n ;
int a[ MAXN ] ;

vector < pair < int , int > > at_row[ MAXN ] ;
vector < int > unblock[ MAXN ] ;

pair < int , int > range[ MAXN ] ;
int prv[ MAXN ] , rnk[ MAXN ] ;
bool emp[ MAXN ] ;
int mx[ MAXN ] ;

class Tree {
public :
    ll tr[ 4 * MAXN ] , lazy[ 4 * MAXN ] ;
    void push_lazy ( int where , int IL , int IR ) {
        tr[ where ] += lazy[ where ] ;
        if ( IL != IR ) {
            lazy[ 2 * where ] += lazy[ where ] ;
            lazy[ 2 * where + 1 ] += lazy[ where ] ;
        }
        lazy[ where ] = 0 ;
    }
    void init ( int where , int IL , int IR ) {
        tr[ where ] = 0 ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int CURL , int CURR , ll add ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            lazy[ where ] += add ;
            push_lazy ( where , IL , IR ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        update ( 2 * where , IL , mid , CURL , CURR , add ) ;
        update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , add ) ;
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    ll query ( int where , int IL , int IR , int CURL , int CURR ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL > IR || CURL > CURR ) { return 0 ; }
        if ( IR < CURL || CURR < IL ) { return 0 ; }
        if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return max ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};
Tree w ;
ll ans ;

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 ) {
        if ( rnk[ k1 ] >= rnk[ k2 ] ) {
            rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
            range[ k1 ].first = min ( range[ k1 ].first , range[ k2 ].first ) ;
            range[ k1 ].second = max ( range[ k1 ].second , range[ k2 ].second ) ;
            prv[ k2 ] = k1 ;
        }
        else {
            range[ k2 ].first = min ( range[ k1 ].first , range[ k2 ].first ) ;
            range[ k2 ].second = max ( range[ k1 ].second , range[ k2 ].second ) ;
            prv[ k1 ] = k2 ;
        }
    }
}

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        unblock[ a[ i ] + 1 ].push_back ( i ) ;
    }
    int m ; cin >> m ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        int x , y , val ;
        cin >> x >> y >> val ;
        at_row[ y ].push_back ( { x , val } ) ;
        ans += val ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        range[ i ] = { i , i } ;
        prv[ i ] = -1 , rnk[ i ] = 0 ;
    }
}

void solve ( ) {
    w.init ( 1 , 1 , n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( auto pos : unblock[ i ] ) {
            ll upd_l = 0 , upd_r = 0 ;
            ll sm = 0 ;
            if ( emp[ pos - 1 ] == true ) {
                int root = get ( pos - 1 ) ;
                upd_r = w.query ( 1 , 1 , n , range[ root ].first , range[ root ].second ) ;
                sm += upd_r ;
            }
            if ( emp[ pos + 1 ] == true ) {
                int root = get ( pos + 1 ) ;
                upd_l = w.query ( 1 , 1 , n , range[ root ].first , range[ root ].second ) ;
                sm += upd_l ;
            }
            if ( emp[ pos - 1 ] == true ) {
                int root = get ( pos - 1 ) ;
                w.update ( 1 , 1 , n , range[ root ].first , range[ root ].second , upd_l ) ;
                unite ( pos - 1 , pos ) ;
            }
            if ( emp[ pos + 1 ] == true ) {
                int root = get ( pos + 1 ) ;
                w.update ( 1 , 1 , n , range[ root ].first , range[ root ].second , upd_r ) ;
                unite ( pos , pos + 1 ) ;
            }
            w.update ( 1 , 1 , n , pos , pos , sm ) ;
            emp[ pos ] = true ;
        }
        for ( auto [ x , val ] : at_row[ i ] ) {
            if ( mx[ x ] < val ) {
                w.update ( 1 , 1 , n , x , x , val - mx[ x ] ) ;
                mx[ x ] = val ;
            }
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( get ( i ) == i && emp[ i ] == true ) {
            ans -= w.query ( 1 , 1 , n , range[ i ].first , range[ i ].second ) ;
        }
    }
    cout << ans << "\n" ;
}

int main ( ) {
    //freopen ( "dictionary.in" , "r" , stdin ) ;
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Compilation message (stderr)

constellation3.cpp: In function 'void solve()':
constellation3.cpp:135:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |         for ( auto [ x , val ] : at_row[ i ] ) {
      |                    ^

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65