# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
896203 | NeroZein | Road Construction (JOI21_road_construction) | C++17 | 1229 ms | 11784 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
a[i] = make_pair(x + y, y - x); // rotate 45 degress
}
sort(a.begin(), a.end());
long long lo = 0, hi = 4e9;
while (lo < hi) {
long long mid = (lo + hi) / 2;
int p = 0, cnt = 0;
multiset<long long> se;
for (int i = 0; i < n && cnt < k; ++i) {
auto [x, y] = a[i];
while (p < i && (long long) x - a[p].first > mid) {
se.erase(se.find(a[p].second));
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |