oj.uz

Submission #540911

# Submission time Handle Problem Language Result Execution time Memory
540911 2022-03-22T00:22:40 Z chonka Road Construction (JOI21_road_construction) C++
100 / 100
 2718 ms 39548 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

#define MAXN 250007

int n , k ;
pair < ll , ll > a[ MAXN ] ;
int ord[ MAXN ] , mx_coord ;


class Tree {
public :
    int tr[ MAXN ] ;
    void init ( ) {
        for ( int i = 0 ; i <= mx_coord ; ++ i ) {
            tr[ i ] = 0 ;
        }
    }
    void update ( int wh , int x ) {
        for ( int i = wh ; i <= mx_coord ; i += ( i & ( -i ) ) ) {
            tr[ i ] += x ;
        }
    }
    int query ( int wh ) {
        int ret = 0 ;
        for ( int i = wh ; i > 0 ; i -= ( i & ( -i ) ) ) {
            ret += tr[ i ] ;
        }
        return ret ;
    }
};
Tree w ;

set < ll > s ;
vector < ll > els ;
map < ll , ll > cm ;
void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int x , y ;
        cin >> x >> y ;
        a[ i ] = { x + y , x - y } ;
        s.insert ( a[ i ].second ) ;
    }
    sort ( a + 1 , a + n + 1 ) ;
    int tp = 0 ;
    for ( auto val : s ) {
        cm[ val ] = ++ tp ;
        els.push_back ( val ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        ord[ i ] = cm[ a[ i ].second ] ;
    }
    mx_coord = tp ;
}


bool f ( long long sr ) {
    w.init ( ) ;
    int st = 0 ;
    int cnt = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        while ( 0LL + a[ i ].first - a[ st + 1 ].first > sr ) {
            w.update ( ord[ st + 1 ] , -1 ) ;
            ++ st ;
        }
        auto lw = lower_bound ( els.begin ( ) , els.end ( ) , a[ i ].second - sr ) - els.begin ( ) + 1 ;
        auto hg = upper_bound ( els.begin ( ) , els.end ( ) , a[ i ].second + sr ) - els.begin ( ) + 1 ;
        -- hg ;
        cnt += w.query ( hg ) - w.query ( lw - 1 ) ;
        w.update ( ord[ i ] , 1 ) ;
        if ( cnt >= k ) { return true ; }
    }
    return false ;
}

set < pair < ll , int > > aux ;
vector < ll > ans ;

void calc ( long long sr ) {
    int st = 0 ;
    int cnt = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        while ( 0LL + a[ i ].first - a[ st + 1 ].first > sr ) {
            aux.erase ( { a[ st + 1 ].second , st + 1 } ) ;
            ++ st ;
        }
        if ( aux.empty ( ) == false ) { 
            auto it1 = aux.lower_bound ( { a[ i ].second , -1 } ) ;
            auto it2 = it1 ;

            while ( it1 != aux.end ( ) ) {
                if ( it1->first - a[ i ].second > sr ) { break ; }
                ans.push_back ( max ( it1->first - a[ i ].second , a[ i ].first - a[ it1->second ].first ) ) ;
                ++ cnt ;
                ++ it1 ;
            }
            if ( it2 != aux.begin ( ) ) {
                -- it2 ;
                while ( 1 ) {
                    if ( a[ i ].second - it2->first > sr ) { break ; }
                    ans.push_back ( max ( a[ i ].second - it2->first , a[ i ].first - a[ it2->second ].first ) ) ;
                    ++ cnt ;
                    if ( it2 == aux.begin ( ) ) { break ; }
                    -- it2 ;
                }
            }
        }
        aux.insert ( { a[ i ].second , i } ) ;
    }
    while ( cnt < k ) {
        ++ cnt ;
        ans.push_back ( sr + 1 ) ;
    }
    sort ( ans.begin ( ) , ans.end ( ) ) ;
    for ( int i = 0 ; i < k ; ++ i ) {
        cout << ans[ i ] << "\n" ;
    }
}

void solve ( ) {
    long long l , r , mid ;
    l = 1 , r = 4e9 ;
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( f ( mid ) == true ) { r = mid ; }
        else { l = mid ; }
    }
    while ( f ( r ) == true ) { -- r ; }
    calc ( r ) ;
}

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 ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5064 KB Output is correct
2 Correct 43 ms 5148 KB Output is correct
3 Correct 41 ms 5096 KB Output is correct
4 Correct 38 ms 5176 KB Output is correct
5 Correct 39 ms 4096 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 38740 KB Output is correct
2 Correct 908 ms 38852 KB Output is correct
3 Correct 37 ms 5048 KB Output is correct
4 Correct 829 ms 38644 KB Output is correct
5 Correct 785 ms 38844 KB Output is correct
6 Correct 725 ms 38800 KB Output is correct
7 Correct 715 ms 38680 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 35488 KB Output is correct
2 Correct 1651 ms 35568 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 656 ms 35472 KB Output is correct
5 Correct 322 ms 5284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 35488 KB Output is correct
2 Correct 1651 ms 35568 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 656 ms 35472 KB Output is correct
5 Correct 322 ms 5284 KB Output is correct
6 Correct 1777 ms 35548 KB Output is correct
7 Correct 1686 ms 35656 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1756 ms 33204 KB Output is correct
11 Correct 537 ms 35732 KB Output is correct
12 Correct 357 ms 5548 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5064 KB Output is correct
2 Correct 43 ms 5148 KB Output is correct
3 Correct 41 ms 5096 KB Output is correct
4 Correct 38 ms 5176 KB Output is correct
5 Correct 39 ms 4096 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1026 ms 18552 KB Output is correct
8 Correct 976 ms 18540 KB Output is correct
9 Correct 40 ms 5176 KB Output is correct
10 Correct 776 ms 16144 KB Output is correct
11 Correct 546 ms 15304 KB Output is correct
12 Correct 204 ms 6392 KB Output is correct
13 Correct 229 ms 4984 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5064 KB Output is correct
2 Correct 43 ms 5148 KB Output is correct
3 Correct 41 ms 5096 KB Output is correct
4 Correct 38 ms 5176 KB Output is correct
5 Correct 39 ms 4096 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 943 ms 38740 KB Output is correct
8 Correct 908 ms 38852 KB Output is correct
9 Correct 37 ms 5048 KB Output is correct
10 Correct 829 ms 38644 KB Output is correct
11 Correct 785 ms 38844 KB Output is correct
12 Correct 725 ms 38800 KB Output is correct
13 Correct 715 ms 38680 KB Output is correct
14 Correct 1368 ms 35488 KB Output is correct
15 Correct 1651 ms 35568 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 656 ms 35472 KB Output is correct
18 Correct 322 ms 5284 KB Output is correct
19 Correct 1777 ms 35548 KB Output is correct
20 Correct 1686 ms 35656 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1756 ms 33204 KB Output is correct
24 Correct 537 ms 35732 KB Output is correct
25 Correct 357 ms 5548 KB Output is correct
26 Correct 1026 ms 18552 KB Output is correct
27 Correct 976 ms 18540 KB Output is correct
28 Correct 40 ms 5176 KB Output is correct
29 Correct 776 ms 16144 KB Output is correct
30 Correct 546 ms 15304 KB Output is correct
31 Correct 204 ms 6392 KB Output is correct
32 Correct 229 ms 4984 KB Output is correct
33 Correct 2718 ms 39548 KB Output is correct
34 Correct 2553 ms 39544 KB Output is correct
35 Correct 2388 ms 31520 KB Output is correct
36 Correct 391 ms 9104 KB Output is correct
37 Correct 381 ms 9368 KB Output is correct
38 Correct 511 ms 7904 KB Output is correct