oj.uz

Submission #573416

# Submission time Handle Problem Language Result Execution time Memory
573416 2022-06-06T15:07:12 Z chonka Team Contest (JOI22_team) C++
0 / 100
 1362 ms 37112 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 13 ms 28512 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 13 ms 28524 KB Output is correct
8 Correct 13 ms 28468 KB Output is correct
9 Correct 13 ms 28428 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28516 KB Output is correct
12 Correct 13 ms 28436 KB Output is correct
13 Correct 13 ms 28520 KB Output is correct
14 Correct 13 ms 28488 KB Output is correct
15 Incorrect 13 ms 28568 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 13 ms 28512 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 13 ms 28524 KB Output is correct
8 Correct 13 ms 28468 KB Output is correct
9 Correct 13 ms 28428 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28516 KB Output is correct
12 Correct 13 ms 28436 KB Output is correct
13 Correct 13 ms 28520 KB Output is correct
14 Correct 13 ms 28488 KB Output is correct
15 Incorrect 13 ms 28568 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28436 KB Output is correct
2 Correct 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 15 ms 28504 KB Output is correct
6 Correct 12 ms 28520 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 15 ms 28424 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 1362 ms 37112 KB Output is correct
12 Incorrect 858 ms 34144 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28436 KB Output is correct
2 Correct 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 15 ms 28504 KB Output is correct
6 Correct 12 ms 28520 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 15 ms 28424 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 1362 ms 37112 KB Output is correct
12 Incorrect 858 ms 34144 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28436 KB Output is correct
2 Correct 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 15 ms 28504 KB Output is correct
6 Correct 12 ms 28520 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 15 ms 28424 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 1362 ms 37112 KB Output is correct
12 Incorrect 858 ms 34144 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28436 KB Output is correct
2 Correct 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 15 ms 28504 KB Output is correct
6 Correct 12 ms 28520 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 15 ms 28424 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 16 ms 28500 KB Output is correct
11 Correct 1362 ms 37112 KB Output is correct
12 Incorrect 858 ms 34144 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 13 ms 28512 KB Output is correct
4 Correct 12 ms 28500 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 13 ms 28524 KB Output is correct
8 Correct 13 ms 28468 KB Output is correct
9 Correct 13 ms 28428 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28516 KB Output is correct
12 Correct 13 ms 28436 KB Output is correct
13 Correct 13 ms 28520 KB Output is correct
14 Correct 13 ms 28488 KB Output is correct
15 Incorrect 13 ms 28568 KB Output isn't correct
16 Halted 0 ms 0 KB -