제출 #1037562

#제출 시각아이디문제언어결과실행 시간메모리
1037562juicyRoad Construction (JOI21_road_construction)C++17
12 / 100
716 ms8276 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 25e4 + 5; int n, k; long long res[N]; array<long long, 2> pt[N]; bool check(long long d) { int top = 0; set<array<long long, 2>> st; for (int i = 1, j = 1; i <= n; ++i) { while (pt[i][0] - pt[j][0] > d) { st.erase({pt[j][1], pt[j][0]}); ++j; } for (auto it = st.lower_bound({pt[i][1] - d, pt[i][0] - d}); it != st.end() && (*it)[0] <= pt[i][1] + d; ++it) { res[++top] = max(abs(pt[i][1] - (*it)[0]), pt[i][0] - (*it)[1]); if (top == k) { return 1; } } st.insert({pt[i][1], pt[i][0]}); } return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for (int i = 1; i <= n; ++i) { int x, y; cin >> x >> y; pt[i] = {x + y, x - y}; } sort(pt + 1, pt + n + 1); long long L = 1, R = 4e9, p = R; while (L <= R) { long long md = (L + R) / 2; if (check(md)) { p = md; R = md - 1; } else { L = md + 1; } } check(p); sort(res + 1, res + k + 1); for (int i = 1; i <= k; ++i) { cout << res[i] << "\n"; } return 0; }
#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...