oj.uz

Submission #540890

# Submission time Handle Problem Language Result Execution time Memory
540890 2022-03-21T22:55:34 Z chonka Road Construction (JOI21_road_construction) C++
11 / 100
 10000 ms 570880 KB 
#include<bits/stdc++.h>
using namespace std ;

#define MAXN 250007

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


set < int > ys ;
map < int , int > cm ;

int ctr = 0 ;

priority_queue < long long > hh ;
long long ans[ MAXN ] ;
int mx_coord ;

class Tree {
public :
    multiset < int > small[ 4 * MAXN ] , large[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        small[ where ].clear ( ) ;
        large[ where ].clear ( ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void ins ( int where , int IL , int IR , int pos , int x , int y ) {
        small[ where ].insert ( - x - y ) ;
        large[ where ].insert ( - x + y ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            ins ( 2 * where , IL , mid , pos , x , y ) ;
        }
        else {
            ins ( 2 * where + 1 , mid + 1 , IR , pos , x , y ) ;
        }
    }
    void proc ( int where , int IL , int IR , int CURL , int CURR , long long mx , long long fw , bool fl , bool inc ) {
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            multiset < int > :: iterator it ;
            multiset < int > :: iterator en ;
            if ( fl == true ) { it = small[ where ].begin ( ) , en = small[ where ].end ( ) ; }
            else { it = large[ where ].begin ( ) , en = large[ where ].end ( ) ; }

            while ( it != en ) {
                if ( fw + (*it) > mx ) { return ; }
                -- ctr ;
                if ( inc == false ) { 
                    if ( ctr < 0 ) { return ; }
                }
                else {
                    hh.push ( fw + (*it) ) ;
                    while ( hh.size ( ) > k ) { hh.pop ( ) ; }
                }
                ++ it ;
            }
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        proc ( 2 * where , IL , mid , CURL , CURR , mx , fw , fl , inc ) ;
        proc ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , mx , fw , fl , inc ) ;
    }
};
Tree w ;

bool f ( long long sr , bool inc ) {
    w.init ( 1 , 1 , mx_coord ) ;
    ctr = k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( ctr <= 0 && inc == false ) { return true ; }
        w.proc ( 1 , 1 , mx_coord , 1 , ord[ i ] , sr , 0LL + a[ i ].first + a[ i ].second , true , inc ) ;
        w.proc ( 1 , 1 , mx_coord , ord[ i ] + 1 , mx_coord , sr , 0LL + a[ i ].first - a[ i ].second , false , inc ) ;

        w.ins ( 1 , 1 , mx_coord , ord[ i ] , a[ i ].first , a[ i ].second ) ;
    }
    if ( ctr > 0 ) { return false ; }
    if ( inc == true ) {
        ctr = k ;
        while ( hh.empty ( ) == false ) {
            ans[ ctr -- ] = hh.top ( ) ;
            hh.pop ( ) ;
        }
        for ( int i = 1 ; i <= k ; ++ i ) {
            cout << ans[ i ] << "\n" ;
        }
    }
    return true ;
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
        ys.insert ( a[ i ].second ) ;
    }
    sort ( a + 1 , a + n + 1 ) ;
    int tp = 0 ;
    for ( auto val : ys ) {
        cm[ val ] = ++ tp ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        ord[ i ] = cm[ a[ i ].second ] ;
    }
    mx_coord = tp ;
}

void solve ( ) {
    long long l , r , mid ;
    l = 1 ;
    r = 1 ;
    for ( int i = 1 ; i <= 10 ; ++ i ) { r *= 10 ; }
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( f ( mid , false ) == true ) { r = mid ; }
        else { l = mid ; }
    }
    while ( f ( l , false ) == false ) { ++ l ; }
    f ( l , true ) ;
}

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

Compilation message

road_construction.cpp: In member function 'void Tree::proc(int, int, int, int, int, long long int, long long int, bool, bool)':
road_construction.cpp:60:41: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |                     while ( hh.size ( ) > k ) { hh.pop ( ) ; }
      |                             ~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 101920 KB Output is correct
2 Correct 310 ms 101928 KB Output is correct
3 Correct 254 ms 101692 KB Output is correct
4 Correct 253 ms 101608 KB Output is correct
5 Correct 294 ms 100844 KB Output is correct
6 Correct 89 ms 94924 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3376 ms 128812 KB Output is correct
2 Correct 3403 ms 129008 KB Output is correct
3 Correct 155 ms 100892 KB Output is correct
4 Correct 2924 ms 128696 KB Output is correct
5 Correct 2493 ms 128724 KB Output is correct
6 Correct 2591 ms 128984 KB Output is correct
7 Correct 1751 ms 128344 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10122 ms 570880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10122 ms 570880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 101920 KB Output is correct
2 Correct 310 ms 101928 KB Output is correct
3 Correct 254 ms 101692 KB Output is correct
4 Correct 253 ms 101608 KB Output is correct
5 Correct 294 ms 100844 KB Output is correct
6 Correct 89 ms 94924 KB Output is correct
7 Execution timed out 10117 ms 273004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 101920 KB Output is correct
2 Correct 310 ms 101928 KB Output is correct
3 Correct 254 ms 101692 KB Output is correct
4 Correct 253 ms 101608 KB Output is correct
5 Correct 294 ms 100844 KB Output is correct
6 Correct 89 ms 94924 KB Output is correct
7 Correct 3376 ms 128812 KB Output is correct
8 Correct 3403 ms 129008 KB Output is correct
9 Correct 155 ms 100892 KB Output is correct
10 Correct 2924 ms 128696 KB Output is correct
11 Correct 2493 ms 128724 KB Output is correct
12 Correct 2591 ms 128984 KB Output is correct
13 Correct 1751 ms 128344 KB Output is correct
14 Execution timed out 10122 ms 570880 KB Time limit exceeded
15 Halted 0 ms 0 KB -