oj.uz

Submission #573421

# Submission time Handle Problem Language Result Execution time Memory
573421 2022-06-06T15:12:41 Z chonka Team Contest (JOI22_team) C++
0 / 100
 1050 ms 35996 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 ;
    int lst = 1 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        while ( a[ lst ].x < a[ i ].x ) {
            w_y.update ( 1 , 1 , n , pos_y[ lst ] , lst , a[ lst ].y ) ;
            w_z.update ( 1 , 1 , n , pos_z[ lst ] , lst , a[ lst ].z ) ;
            ++ lst ;
        }
        int l , r , mid ;
        l = 1 , r = w_y.tr[ 1 ].cnt ;
        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 ) ;
            }
        }
    }
    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 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28552 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 12 ms 28500 KB Output is correct
8 Correct 12 ms 28500 KB Output is correct
9 Correct 12 ms 28536 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 12 ms 28428 KB Output is correct
12 Correct 12 ms 28436 KB Output is correct
13 Correct 12 ms 28424 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Incorrect 13 ms 28520 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 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28552 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 12 ms 28500 KB Output is correct
8 Correct 12 ms 28500 KB Output is correct
9 Correct 12 ms 28536 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 12 ms 28428 KB Output is correct
12 Correct 12 ms 28436 KB Output is correct
13 Correct 12 ms 28424 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Incorrect 13 ms 28520 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 28500 KB Output is correct
2 Correct 11 ms 28444 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 12 ms 28496 KB Output is correct
6 Correct 12 ms 28500 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 12 ms 28472 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 12 ms 28500 KB Output is correct
11 Correct 1050 ms 35996 KB Output is correct
12 Incorrect 594 ms 33808 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 28500 KB Output is correct
2 Correct 11 ms 28444 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 12 ms 28496 KB Output is correct
6 Correct 12 ms 28500 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 12 ms 28472 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 12 ms 28500 KB Output is correct
11 Correct 1050 ms 35996 KB Output is correct
12 Incorrect 594 ms 33808 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 28500 KB Output is correct
2 Correct 11 ms 28444 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 12 ms 28496 KB Output is correct
6 Correct 12 ms 28500 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 12 ms 28472 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 12 ms 28500 KB Output is correct
11 Correct 1050 ms 35996 KB Output is correct
12 Incorrect 594 ms 33808 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 28500 KB Output is correct
2 Correct 11 ms 28444 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 12 ms 28496 KB Output is correct
6 Correct 12 ms 28500 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 12 ms 28472 KB Output is correct
9 Correct 13 ms 28500 KB Output is correct
10 Correct 12 ms 28500 KB Output is correct
11 Correct 1050 ms 35996 KB Output is correct
12 Incorrect 594 ms 33808 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 12 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28552 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 12 ms 28500 KB Output is correct
8 Correct 12 ms 28500 KB Output is correct
9 Correct 12 ms 28536 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 12 ms 28428 KB Output is correct
12 Correct 12 ms 28436 KB Output is correct
13 Correct 12 ms 28424 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Incorrect 13 ms 28520 KB Output isn't correct
16 Halted 0 ms 0 KB -