#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 ) {
if ( hh.top ( ) == fw + (*it) ) { return ; }
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 ) {
| ~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
302 ms |
102048 KB |
Output is correct |
| 2 |
Correct |
298 ms |
101916 KB |
Output is correct |
| 3 |
Correct |
263 ms |
101652 KB |
Output is correct |
| 4 |
Correct |
254 ms |
101636 KB |
Output is correct |
| 5 |
Correct |
297 ms |
101048 KB |
Output is correct |
| 6 |
Runtime error |
150 ms |
192500 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3386 ms |
128804 KB |
Output is correct |
| 2 |
Correct |
3495 ms |
128804 KB |
Output is correct |
| 3 |
Correct |
151 ms |
100848 KB |
Output is correct |
| 4 |
Runtime error |
3051 ms |
256792 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10037 ms |
565652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10037 ms |
565652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
302 ms |
102048 KB |
Output is correct |
| 2 |
Correct |
298 ms |
101916 KB |
Output is correct |
| 3 |
Correct |
263 ms |
101652 KB |
Output is correct |
| 4 |
Correct |
254 ms |
101636 KB |
Output is correct |
| 5 |
Correct |
297 ms |
101048 KB |
Output is correct |
| 6 |
Runtime error |
150 ms |
192500 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
302 ms |
102048 KB |
Output is correct |
| 2 |
Correct |
298 ms |
101916 KB |
Output is correct |
| 3 |
Correct |
263 ms |
101652 KB |
Output is correct |
| 4 |
Correct |
254 ms |
101636 KB |
Output is correct |
| 5 |
Correct |
297 ms |
101048 KB |
Output is correct |
| 6 |
Runtime error |
150 ms |
192500 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
