Submission #573416

#	Time	Username	Problem	Language	Result	Execution time	Memory
573416		chonka	Team Contest (JOI22_team)	C++98	0 / 100	1362 ms	37112 KiB

team

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 150007 ;
const int BASE = 150133 ;
ll MOD[ 2 ] = { 1000000007 , 998244353 } ;
ll pw[ 2 ][ MAXN ] ;

int n ;

struct sex {
    int x , y , z ;
};
sex a[ MAXN ] ;
int pos_y[ MAXN ] ;
int pos_z[ MAXN ] ;

struct hsh {
    ll val[ 2 ] ;
    int cnt ;
    hsh ( ) { val[ 0 ] = val[ 1 ] = cnt = 0 ; }
    hsh ( int x ) {
        for ( int i : { 0 , 1 } ) {
            val[ i ] = ( x % MOD[ i ] ) ;
        }
        cnt = 1 ;
    }
};

hsh unite ( hsh p1 , hsh p2 ) {
    hsh ret ;
    ret.cnt = p1.cnt + p2.cnt ;
    for ( int i = 0 ; i < 2 ; ++ i ) {
        ret.val[ i ] = ( p1.val[ i ] * pw[ i ][ p2.cnt ] + p2.val[ i ] ) % MOD[ i ] ;
    }
    return ret ;
}

class Tree {
public :
    hsh tr[ 4 * MAXN ] ;
    int leaves[ MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = hsh ( ) ;
        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 pos , int id , int nw ) {
        if ( IR < pos || pos < IL ) { return ; }
        if ( IL == IR ) {
            tr[ where ] = hsh ( id ) ;
            leaves[ pos ] = nw ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos , id , nw ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos , id , nw ) ;
        }
        tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    hsh query ( int where , int IL , int IR , int cnt ) {
        if ( cnt <= 0 ) { return hsh ( ) ; }
        if ( tr[ where ].cnt <= cnt ) {
            return tr[ where ] ;
        }
        int mid = ( IL + IR ) / 2 ;
        hsh r = query ( 2 * where + 1 , mid + 1 , IR , cnt ) ;
        hsh l = query ( 2 * where , IL , mid , cnt - r.cnt ) ;
        return unite ( l , r ) ;
    }
    int get_kth ( int where , int IL , int IR , int cnt ) {
        if ( cnt <= 0 ) { return -1 ; }
        if ( IL == IR ) { return leaves[ IL ] ; }
        int mid = ( IL + IR ) / 2 ;
        if ( tr[ 2 * where + 1 ].cnt >= cnt ) {
            return get_kth ( 2 * where + 1 , mid + 1 , IR , cnt ) ;
        }
        else {
            return get_kth ( 2 * where , IL , mid , cnt - tr[ 2 * where + 1 ].cnt ) ;
        }
    }
};

Tree w_y , w_z ;

pair < int , int > srt[ MAXN ] ;

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].z ;
    }
    auto cmp = [ & ] ( sex p1 , sex p2 ) {
        return ( p1.x < p2.x ) ;
    };
    for ( int i : { 0 , 1 } ) {
        pw[ i ][ 0 ] = 1 ;
        for ( int j = 1 ; j <= n ; ++ j ) {
            pw[ i ][ j ] = ( pw[ i ][ j - 1 ] * BASE ) % MOD[ i ] ;
        }
    }
    sort ( a + 1 , a + n + 1 , cmp ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        srt[ i ] = { a[ i ].y , i } ;
    }
    sort ( srt + 1 , srt + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        pos_y[ srt[ i ].second ] = i ;
    }

    for ( int i = 1 ; i <= n ; ++ i ) {
        srt[ i ] = { a[ i ].z , i } ;
    }
    sort ( srt + 1 , srt + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        pos_z[ srt[ i ].second ] = i ;
    }
}

bool diff ( int cnt ) {
    hsh h_y = w_y.query ( 1 , 1 , n , cnt ) ;
    hsh h_z = w_z.query ( 1 , 1 , n , cnt ) ;
    if ( h_y.val[ 0 ] != h_z.val[ 0 ] ) { return true ; }
    if ( h_y.val[ 1 ] != h_z.val[ 1 ] ) { return true ; }
    if ( h_y.cnt != h_z.cnt ) { return true ; }
    return false ;
}

void solve ( ) {
    w_y.init ( 1 , 1 , n ) ;
    w_z.init ( 1 , 1 , n ) ;
    int ans = -1 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int l , r , mid ;
        l = 1 , r = i - 1 ;
        if ( r >= 1 && diff ( r ) == true ) {
            while ( r - l > 3 ) {
                mid = ( l + r ) / 2 ;
                if ( diff ( mid ) == true ) { r = mid ; }
                else { l = mid + 1 ; }
            }
            while ( diff ( l ) == false ) { ++ l ; }
            int aux_y = w_y.get_kth ( 1 , 1 , n , l ) ;
            int aux_z = w_z.get_kth ( 1 , 1 , n , l ) ;
            if ( a[ i ].y < aux_y && a[ i ].z < aux_z ) {
                ans = max ( ans , a[ i ].x + aux_y + aux_z ) ;
            }
        }
        w_y.update ( 1 , 1 , n , pos_y[ i ] , i , a[ i ].y ) ;
        w_z.update ( 1 , 1 , n , pos_z[ i ] , i , a[ i ].z ) ;
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t ;
    /// cin >> t ;
    ///scanf ( "%d" , &t ) ;
    t = 1 ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27