Submission #722578

#	Time	Username	Problem	Language	Result	Execution time	Memory
722578		piOOE	Road Construction (JOI21_road_construction)	C++17	100 / 100	2162 ms	13496 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    int n, k;
    cin >> n >> k;

    vector<array<ll, 2>> a(n);

    for (auto &[x, y] : a) {
        cin >> x >> y;
        ll sx = x, sy = y;
        x = sx + sy, y = sx - sy;
    }

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

    vector<ll> res;

    auto solve = [&](ll dist)-> bool {
        res.clear();

        set<pair<ll, int>> st;

        int pnt = 0;

        for (int i = 0; i < n; ++i) {
            auto [x, y] = a[i];

            while (pnt < i && x - a[pnt][0] > dist) {
                st.erase({a[pnt][1], pnt++});
            }

            auto it = st.lower_bound({y - dist, -1});

            while (it != st.end() && it->first <= y + dist) {
                int j = it->second;

                res.push_back(max(a[i][0] - a[j][0], abs(a[i][1] - a[j][1])));

                if (res.size() == k) {
                    return true;
                }

                ++it;
            }

            st.emplace(y, i);
        }

        return false;
    };


    ll ans = 0;

    for (ll x = 1LL << 31; x >= 1; x >>= 1) {
        if (!solve(ans + x)) {
            ans += x;
        }
    }


    solve(ans);

    while (res.size() < k) {
        res.push_back(ans + 1);
    }

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

    for (int i = 0; i < k; ++i) {
        cout << res[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In lambda function:
road_construction.cpp:36:41: warning: operation on 'pnt' may be undefined [-Wsequence-point]
   36 |                 st.erase({a[pnt][1], pnt++});
      |                                      ~~~^~
road_construction.cpp:46:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |                 if (res.size() == k) {
      |                     ~~~~~~~~~~~^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     while (res.size() < k) {
      |            ~~~~~~~~~~~^~~

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