oj.uz

Submission #540892

# Submission time Handle Problem Language Result Execution time Memory
540892 2022-03-21T23:10:22 Z chonka Road Construction (JOI21_road_construction) C++
11 / 100
 10000 ms 565744 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 ) {
                        int aux = hh.top ( ) ;
                        hh.pop ( ) ;
                        if ( aux == fw + (*it) ) { return ; }
                    }
                }
                ++ 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 ) {
      |                             ~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 102064 KB Output is correct
2 Correct 321 ms 101924 KB Output is correct
3 Correct 277 ms 101680 KB Output is correct
4 Correct 252 ms 101716 KB Output is correct
5 Correct 337 ms 100836 KB Output is correct
6 Correct 87 ms 94924 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3488 ms 126000 KB Output is correct
2 Correct 3469 ms 125912 KB Output is correct
3 Correct 163 ms 100952 KB Output is correct
4 Correct 3040 ms 125752 KB Output is correct
5 Correct 2580 ms 128716 KB Output is correct
6 Correct 2622 ms 128944 KB Output is correct
7 Correct 1773 ms 128288 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10056 ms 565744 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 10056 ms 565744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 102064 KB Output is correct
2 Correct 321 ms 101924 KB Output is correct
3 Correct 277 ms 101680 KB Output is correct
4 Correct 252 ms 101716 KB Output is correct
5 Correct 337 ms 100836 KB Output is correct
6 Correct 87 ms 94924 KB Output is correct
7 Execution timed out 10049 ms 271388 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 102064 KB Output is correct
2 Correct 321 ms 101924 KB Output is correct
3 Correct 277 ms 101680 KB Output is correct
4 Correct 252 ms 101716 KB Output is correct
5 Correct 337 ms 100836 KB Output is correct
6 Correct 87 ms 94924 KB Output is correct
7 Correct 3488 ms 126000 KB Output is correct
8 Correct 3469 ms 125912 KB Output is correct
9 Correct 163 ms 100952 KB Output is correct
10 Correct 3040 ms 125752 KB Output is correct
11 Correct 2580 ms 128716 KB Output is correct
12 Correct 2622 ms 128944 KB Output is correct
13 Correct 1773 ms 128288 KB Output is correct
14 Execution timed out 10056 ms 565744 KB Time limit exceeded
15 Halted 0 ms 0 KB -