Submission #1124539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124539		Error42	Road Construction (JOI21_road_construction)	C++20	6 / 100	371 ms	9640 KiB

road_construction

#include <algorithm>
#include <climits>
#include <compare>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

using ll = long long;

ll const INF = LLONG_MAX / 3;

struct point {
    ll x, y;

    auto operator <=>(point const& rhs) const = default;

    point swapped() const {
        return { y, x };
    }

    ll dist(point const& rhs) const {
        return max(abs(x - rhs.x), abs(y - rhs.y));
    }
};

vector<ll> attempt(vector<point> const& cities, ll const dist, ll const k) {
    set<point> possible;

    ll i = 0;

    vector<ll> ret;

    for (ll j = 0; j < cities.size(); j++) {
        while (cities[j].x - cities[i].x > dist) {
            possible.erase(cities[i].swapped());
            i++;
        }

        auto const lo = possible.lower_bound({ cities[j].y - dist, -INF });
        auto const hi = possible.lower_bound({ cities[j].y + dist, INF });

        for (auto it = lo; it != hi; ++it) {
            ret.push_back(cities[j].swapped().dist(*it));

            if (ret.size() == k)
                return ret;
        }

        possible.insert(cities[j].swapped());
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;

    vector<point> cities(n);
    for (point& p : cities) {
        ll x, y;
        cin >> x >> y;

        p = { x + y, x - y };
    }

    sort(cities.begin(), cities.end());

    ll lo = 0;
    ll hi = 2'000'000'010;

    while (lo + 1 != hi) {
        ll const mid = (lo + hi) / 2;

        auto const result = attempt(cities, mid, k);

        if (result.size() >= k)
            hi = mid;
        else
            lo = mid;
    }

    auto ans = attempt(cities, lo, k);
    sort(ans.begin(), ans.end());
    ans.resize(k, lo + 1);

    for (ll const& x : ans)
        cout << x << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35