Submission #1115998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115998		Zero_OP	Road Construction (JOI21_road_construction)	C++14	100 / 100	1210 ms	19904 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<pair<long long, long long>> diags;
    for(int i = 0; i < N; ++i){
        long long x, y;
        cin >> x >> y;
        diags.emplace_back(x + y, x - y);
    }

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

    vector<pair<long long, long long>> pts;
    for(int i = 0; i < N; ++i){
        long long x = (diags[i].first + diags[i].second) / 2;
        long long y = diags[i].first - x;
        pts.emplace_back(x, y);
    }

    auto get_dist = [&](int i, int j) -> long long{
        return abs(pts[i].first - pts[j].first) + abs(pts[i].second - pts[j].second);
    };

    auto f = [&](long long d){
        multiset<long long> st;
        int cnt = 0;
        for(int i = 0, j = 0; i < N; ++i){
            while(j < i && diags[i].first - diags[j].first > d){
                st.erase(st.lower_bound(diags[j].second));
                ++j;
            }

            for(auto it = st.lower_bound(diags[i].second - d); it != st.end() && *it <= diags[i].second + d; ++it){
                ++cnt;
                if(cnt >= K) return false;
            }

            st.insert(diags[i].second);
        }
        return true;
    };

    long long l = 1, r = 4e9 + 10, ans = 0;
    while(l <= r){
        long long mid = l + r >> 1;
        if(f(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    vector<long long> dists;
    multiset<pair<long long, int>> st;
    const int inf = 1e9;

    for(int i = 0, j = 0; i < N; ++i){
        while(j < i && diags[i].first - diags[j].first > ans){
            st.erase({diags[j].second, j});
            ++j;
        }

        for(auto it = st.lower_bound({diags[i].second - ans, -inf}); it != st.end() && it -> first <= diags[i].second + ans; ++it){
            dists.emplace_back(get_dist(i, it -> second));
        }

        st.insert({diags[i].second, i});
    }

    assert((int)dists.size() < K);
    int n_last = K - (int)dists.size();
    for(int i = 0; i < n_last; ++i) dists.emplace_back(ans + 1);
    sort(dists.begin(), dists.end());

    for(auto it : dists) cout << it << '\n';
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:53:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         long long mid = l + r >> 1;
      |                         ~~^~~

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