Submission #1157948

#TimeUsernameProblemLanguageResultExecution timeMemory
1157948KluydQRoad Construction (JOI21_road_construction)C++20
5 / 100
10109 ms829168 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define respagold ios_base::sync_with_stdio(0), cin.tie(0); #define int long long #define ll long long #define int2 __int128_t #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define pb push_back #define ins insert #define lb lower_bound #define ub upper_bound #define pii pair <int, int> #define mkp make_pair using namespace std; using namespace __gnu_pbds; template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 3e5 + 123; const int inf = 1e18; const int mod = 1e9 + 7; const double eps = 1e-13; int n, m, k, z, x[N], y[N], rx[N], ry[N], nashel, ans; vector <int> answ; mt19937 rng( chrono::steady_clock::now().time_since_epoch().count()); int rand( int l, int r ) { uniform_int_distribution <int> uid( l, r ); return uid( rng ); } vector <int> ordx, ordy, del; ordered_multiset <int> st1, st2; bool cmpx( int a, int b ) { return x[a] < x[b]; } bool cmpy( int a, int b ) { return y[a] < y[b]; } ordered_multiset <int> t[4 * N][2]; void update( int p, int x, int tp, int v = 1, int tl = 1, int tr = n ) { t[v][tp].ins(x); if( tl == tr ) return; int tm = tl + tr >> 1; if( p <= tm ) update( p, x, tp, v + v, tl, tm ); else update( p, x, tp, v + v + 1, tm + 1, tr ); } int get( int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n ) { if( tl > r || l > tr ) return 0; if( l <= tl && tr <= r ) { if( !nashel ) return sz(t[v][tp]) - t[v][tp].order_of_key(x); else { int xx = sz(t[v][tp]) - t[v][tp].order_of_key(x); if( xx == 0 ) return 0; del.clear(); int kuda = sz(t[v][tp]) - xx; while( sz(t[v][tp]) > kuda && x - *t[v][tp].rbegin() + ans < ans ) del.pb(*t[v][tp].rbegin()), t[v][tp].erase(t[v][tp].rbegin()); for( auto i : del ) t[v][tp].ins(i), answ.pb(x - i + ans); return xx; } } int tm = tl + tr >> 1; return get( l, r, x, tp, v + v, tl, tm ) + get( l, r, x, tp, v + v + 1, tm + 1, tr ); } int check( int dist ) { int res = 0; st1.clear(); st2.clear(); FOR( i, 1, n, 1 ) { int px = ordx[i - 1], py = ry[px]; // x[px] + y[px] - ne <= dist // x[px] + y[px] - dist <= ne res += get( 1, py - 1, x[px] + y[px] - dist, 0 ); res += get( py + 1, n, x[px] - y[px] - dist, 1 ); update( py, x[px] + y[px], 0 ); update( py, x[px] - y[px], 1 ); } FOR( i, 1, 4 * n, 1 ) t[i][1].clear(), t[i][0].clear(); return res; } void solve() { cin >> n >> k; vector <int> v; FOR( i, 1, n, 1 ) { cin >> x[i] >> y[i]; ordx.pb(i); ordy.pb(i); } sort( all(ordx), cmpx ); sort( all(ordy), cmpy ); FOR( i, 1, n, 1 ) ry[ordy[i - 1]] = i; int l = 0, r = 4e9; ans = 4e9; while( l <= r ) { int md = l + r >> 1; if( check(md) >= k ) r = md - 1, ans = md; else l = md + 1; } nashel = 1; FOR( i, 1, n, 1 ) { int px = ordx[i - 1], py = ry[px]; get( 1, py - 1, x[px] + y[px] - ans, 0 ); get( py + 1, n, x[px] - y[px] - ans, 1 ); update( py, x[px] + y[px], 0 ); update( py, x[px] - y[px], 1 ); } sort( all( answ )); FOR( i, 0, min( k - 1, sz(answ) - 1 ), 1 ) cout << answ[i] << '\n'; FOR( i, sz(answ), k - 1, 1 ) cout << ans << '\n'; } signed main() { // freopen("connect.in", "r", stdin); // freopen("connect.out", "w", stdout); respagold int test = 1; if( !test ) cin >> test; while( test -- ) { solve(); } } // solved by KluydQ
#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...