Submission #890507

#TimeUsernameProblemLanguageResultExecution timeMemory
890507LucaIlieRoad Construction (JOI21_road_construction)C++17
100 / 100
4747 ms17252 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct point { int x, y; }; struct aa { int i, val; bool operator < ( const aa &a ) const { if ( val == a.val ) return i < a.i; return val < a.val; } }; const int MAX_N = 2.5e5; const int INF = 2e9 + 1; point v[MAX_N]; struct AIB { vector<int> pos; vector<int> aib; void init() { pos.clear(); aib.clear(); } void add( int i ) { pos.push_back( i ); } void prep() { pos.push_back( -INF ); sort( pos.begin(), pos.end() ); pos.resize( unique( pos.begin(), pos.end() ) - pos.begin() ); aib.resize( pos.size() ); } void clear() { for ( int i = 0; i < aib.size(); i++ ) aib[i] = 0; } void update( int i, int x ) { int l = 0, r = pos.size(); while ( r - l > 1 ) { int p = (l + r) / 2; if ( pos[p] > i ) r = p; else l = p; } i = l; while ( i < aib.size() ) { aib[i] += x; i += (i & -i); } } int query( int i ) { int l = 0, r = pos.size(); while ( r - l > 1 ) { int p = (l + r) / 2; if ( pos[p] > i ) r = p; else l = p; } i = l; int s = 0; while ( i > 0 ) { s += aib[i]; i -= (i & -i); } return s; } } points; set<aa> s; signed main() { ios_base::sync_with_stdio( false ); cin.tie( NULL ); cout.tie( NULL ); int n, k; cin >> n >> k; for ( int i = 0; i < n; i++ ) cin >> v[i].x >> v[i].y; sort( v, v + n, []( point a, point b ) { if ( a.x + a.y == b.x + b.y ) return a.x - a.y < b.x - b.y; return a.x + a.y < b.x + b.y; } ); points.init(); for ( int i = 0; i < n; i++ ) points.add( v[i].x - v[i].y ); points.prep(); long long ld = 0, rd = 2 * INF; while ( rd - ld > 1 ) { long long d = (ld + rd) / 2; long long pairs = 0; points.clear(); int j = 0; for ( int i = 0; i < n; i++ ) { while ( (v[i].x + v[i].y) - (v[j].x + v[j].y) > d ) { points.update( v[j].x - v[j].y, -1 ); j++; } pairs += points.query( v[i].x - v[i].y + d ) - points.query( v[i].x - v[i].y - d - 1 ); points.update( v[i].x - v[i].y, 1 ); } if ( pairs < k ) ld = d; else rd = d; } long long d = ld; vector<long long> sol; int j = 0; for ( int i = 0; i < n; i++ ) { while ( (v[i].x + v[i].y) - (v[j].x + v[j].y) > d ) { s.erase( { j, v[j].x - v[j].y } ); j++; } auto it = s.lower_bound( { -1, v[i].x - v[i].y - d } ); while ( it != s.end() && it->val <= v[i].x - v[i].y + d ) { int j = it->i; sol.push_back( abs( v[i].x - v[j].x ) + abs( v[i].y - v[j].y ) ); it++; } s.insert( { i, v[i].x - v[i].y } ); } while ( sol.size() < k ) sol.push_back( d + 1 ); sort( sol.begin(), sol.end() ); for( long long x: sol ) cout << x << "\n"; return 0; }

Compilation message (stderr)

road_construction.cpp: In member function 'void AIB::clear()':
road_construction.cpp:46:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for ( int i = 0; i < aib.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB::update(long long int, long long int)':
road_construction.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:155:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  155 |     while ( sol.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...