oj.uz

Submission #540909

# Submission time Handle Problem Language Result Execution time Memory
540909 2022-03-22T00:07:05 Z chonka Road Construction (JOI21_road_construction) C++
45 / 100
 10000 ms 37208 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 ;
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 ;
    }
    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 = s.lower_bound ( a[ i ].second - sr ) ;
        auto hg = s.upper_bound ( a[ i ].second + sr ) ;
        -- hg ;
        cnt += w.query ( cm[ *hg ] ) - w.query ( cm[ *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 = 1e10 ;
    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 48 ms 5196 KB Output is correct
2 Correct 49 ms 5064 KB Output is correct
3 Correct 41 ms 5208 KB Output is correct
4 Correct 41 ms 5164 KB Output is correct
5 Correct 42 ms 4008 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 2013 ms 37208 KB Output is correct
2 Correct 1996 ms 37184 KB Output is correct
3 Correct 36 ms 4976 KB Output is correct
4 Correct 1705 ms 36964 KB Output is correct
5 Correct 1725 ms 37172 KB Output is correct
6 Correct 1584 ms 37148 KB Output is correct
7 Correct 1246 ms 36372 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5731 ms 33968 KB Output is correct
2 Correct 7456 ms 33820 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 955 ms 33820 KB Output is correct
5 Correct 708 ms 5576 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5731 ms 33968 KB Output is correct
2 Correct 7456 ms 33820 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 955 ms 33820 KB Output is correct
5 Correct 708 ms 5576 KB Output is correct
6 Execution timed out 10044 ms 33824 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5196 KB Output is correct
2 Correct 49 ms 5064 KB Output is correct
3 Correct 41 ms 5208 KB Output is correct
4 Correct 41 ms 5164 KB Output is correct
5 Correct 42 ms 4008 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 4062 ms 17848 KB Output is correct
8 Correct 4163 ms 17856 KB Output is correct
9 Correct 40 ms 5176 KB Output is correct
10 Correct 2872 ms 15608 KB Output is correct
11 Correct 1816 ms 14764 KB Output is correct
12 Correct 353 ms 6572 KB Output is correct
13 Correct 308 ms 5108 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5196 KB Output is correct
2 Correct 49 ms 5064 KB Output is correct
3 Correct 41 ms 5208 KB Output is correct
4 Correct 41 ms 5164 KB Output is correct
5 Correct 42 ms 4008 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2013 ms 37208 KB Output is correct
8 Correct 1996 ms 37184 KB Output is correct
9 Correct 36 ms 4976 KB Output is correct
10 Correct 1705 ms 36964 KB Output is correct
11 Correct 1725 ms 37172 KB Output is correct
12 Correct 1584 ms 37148 KB Output is correct
13 Correct 1246 ms 36372 KB Output is correct
14 Correct 5731 ms 33968 KB Output is correct
15 Correct 7456 ms 33820 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 955 ms 33820 KB Output is correct
18 Correct 708 ms 5576 KB Output is correct
19 Execution timed out 10044 ms 33824 KB Time limit exceeded
20 Halted 0 ms 0 KB -