Submission #540892

#TimeUsernameProblemLanguageResultExecution timeMemory
540892chonkaRoad Construction (JOI21_road_construction)C++98
11 / 100
10056 ms565744 KiB
#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 (stderr)

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 ) {
      |                             ~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...