Submission #540911

#	Time	Username	Problem	Language	Result	Execution time	Memory
540911		chonka	Road Construction (JOI21_road_construction)	C++98	100 / 100	2718 ms	39548 KiB

road_construction

#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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35