Submission #968614

#TimeUsernameProblemLanguageResultExecution timeMemory
968614LOLOLORoad Construction (JOI21_road_construction)C++17
100 / 100
1592 ms15308 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 3e5 + 50; vector <ll> lst; vector <pair <ll, ll>> point; int lim; void solve(ll k) { set <pair <ll, ll>> save; lst.clear(); int j = 0; for (int i = 0; i < sz(point); i++) { while (point[i].f - point[j].f > k) { save.erase({point[j].s, j}); j++; } auto it = save.lower_bound({point[i].s - k, -1}); while (it != save.end()) { if (abs(it -> f - point[i].s) > k) break; lst.pb(max(abs(point[it -> s].s - point[i].s), abs(point[i].f - point[it -> s].f))); if (sz(lst) >= lim) return; it = next(it); } save.insert({point[i].s, i}); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n >> lim; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; point.pb({x + y, x - y}); } sort(all(point)); ll l = 0, r = 4e9, m, ans; while (l <= r) { m = (l + r) / 2; solve(m); if (sz(lst) >= lim) { ans = m; r = m - 1; } else { l = m + 1; } } solve(ans - 1); while (sz(lst) < lim) lst.pb(ans); sort(all(lst)); for (auto x : lst) cout << x << '\n'; return 0; } /* 10 10 10 -8 7 2 7 -8 -3 -6 -2 1 -8 6 8 -1 2 4 6 -6 2 -1 */
#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...