oj.uz

Submission #573420

# Submission time Handle Problem Language Result Execution time Memory
573420 2022-06-06T15:10:47 Z chonka Team Contest (JOI22_team) C++
0 / 100
 1111 ms 36784 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 = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        while ( lst < i && 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 13 ms 28532 KB Output is correct
3 Correct 14 ms 28512 KB Output is correct
4 Correct 13 ms 28448 KB Output is correct
5 Correct 15 ms 28520 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 16 ms 28524 KB Output is correct
8 Correct 17 ms 28500 KB Output is correct
9 Correct 14 ms 28500 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28496 KB Output is correct
12 Correct 15 ms 28504 KB Output is correct
13 Correct 16 ms 28516 KB Output is correct
14 Correct 17 ms 28500 KB Output is correct
15 Incorrect 18 ms 28456 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 13 ms 28532 KB Output is correct
3 Correct 14 ms 28512 KB Output is correct
4 Correct 13 ms 28448 KB Output is correct
5 Correct 15 ms 28520 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 16 ms 28524 KB Output is correct
8 Correct 17 ms 28500 KB Output is correct
9 Correct 14 ms 28500 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28496 KB Output is correct
12 Correct 15 ms 28504 KB Output is correct
13 Correct 16 ms 28516 KB Output is correct
14 Correct 17 ms 28500 KB Output is correct
15 Incorrect 18 ms 28456 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28524 KB Output is correct
2 Correct 15 ms 28512 KB Output is correct
3 Correct 15 ms 28528 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 13 ms 28516 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 14 ms 28524 KB Output is correct
8 Correct 13 ms 28500 KB Output is correct
9 Correct 24 ms 28500 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 1111 ms 36784 KB Output is correct
12 Incorrect 626 ms 34152 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28524 KB Output is correct
2 Correct 15 ms 28512 KB Output is correct
3 Correct 15 ms 28528 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 13 ms 28516 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 14 ms 28524 KB Output is correct
8 Correct 13 ms 28500 KB Output is correct
9 Correct 24 ms 28500 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 1111 ms 36784 KB Output is correct
12 Incorrect 626 ms 34152 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28524 KB Output is correct
2 Correct 15 ms 28512 KB Output is correct
3 Correct 15 ms 28528 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 13 ms 28516 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 14 ms 28524 KB Output is correct
8 Correct 13 ms 28500 KB Output is correct
9 Correct 24 ms 28500 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 1111 ms 36784 KB Output is correct
12 Incorrect 626 ms 34152 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28524 KB Output is correct
2 Correct 15 ms 28512 KB Output is correct
3 Correct 15 ms 28528 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 13 ms 28516 KB Output is correct
6 Correct 15 ms 28524 KB Output is correct
7 Correct 14 ms 28524 KB Output is correct
8 Correct 13 ms 28500 KB Output is correct
9 Correct 24 ms 28500 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 1111 ms 36784 KB Output is correct
12 Incorrect 626 ms 34152 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 13 ms 28532 KB Output is correct
3 Correct 14 ms 28512 KB Output is correct
4 Correct 13 ms 28448 KB Output is correct
5 Correct 15 ms 28520 KB Output is correct
6 Correct 13 ms 28524 KB Output is correct
7 Correct 16 ms 28524 KB Output is correct
8 Correct 17 ms 28500 KB Output is correct
9 Correct 14 ms 28500 KB Output is correct
10 Correct 13 ms 28524 KB Output is correct
11 Correct 13 ms 28496 KB Output is correct
12 Correct 15 ms 28504 KB Output is correct
13 Correct 16 ms 28516 KB Output is correct
14 Correct 17 ms 28500 KB Output is correct
15 Incorrect 18 ms 28456 KB Output isn't correct
16 Halted 0 ms 0 KB -