Submission #575471

#	Time	Username	Problem	Language	Result	Execution time	Memory
575471		rainliofficial	Road Construction (JOI21_road_construction)	C++17	100 / 100	2011 ms	19508 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(x) (int)x.size()
#define f first
#define s second

/* 
Date: 2022/06/10
Problem Link: https://oj.uz/problem/view/JOI21_road_construction
Topic(s): Binary search, sorting
Time Spent: 
Solution Outline:
- The distance between two points can be written as max(abs((xi + yi) - (xj + yj)), abs((xi - yi) - (xj - yj)))
Binary search on v, which is the kth largest value. We have to check whether there more or less than k roads with
cost <= v. 
- Maintain a sliding window of size v. 
- Sort the points by xi + yi. For a point i, remove all points j that has xj + yj further than v units away.
- Put xi - yi into the set. 
- We know all js that came before i must have xi + yi - (xj + yj) <= v. So we can simply call lower_bound on the set
with xi - yi - v and vi - vi + v. The range that it gives us will be the amount of points within v distance of i. 
*/

const int MAXN = 2e5+5;
int n, k;
vector<pll> arr;
vector<ll> res;

ll sum(const pll& a){
    return a.f + a.s;
}
ll dif(const pll& a){
    return a.f - a.s;
}


bool check(ll v, bool upd){
    int l = 0;
    auto cmp = [](const pll& a, const pll& b){
        if (dif(a) == dif(b)){
            return a < b;
        }else{
            return a.f - a.s < b.f - b.s;
        }
    };
    set<pll, decltype(cmp)> set(cmp);
    ll ans = 0;
    for (int i=0; i<n; i++){
        while (l < n && sum(arr[i]) - sum(arr[l]) > v){
            set.erase(arr[l]);
            l++;
        }
        auto inc = set.lower_bound(arr[i]);
        auto dec = inc;
        while (inc != set.end() && dif(*inc) - dif(arr[i]) <= v){
            if (upd) res.push_back(abs(arr[i].f - (*inc).f) + abs(arr[i].s - (*inc).s));
            inc++;
            ans++;
            if (!upd && ans >=k){
                return true;
            }
        }
        while (dec != set.begin() && dif(arr[i]) - dif(*prev(dec)) <= v){
            dec--;
            if (upd) res.push_back(abs(arr[i].f - (*dec).f) + abs(arr[i].s - (*dec).s));
            ans++;
            if (!upd && ans >=k){
                return true;
            }
        }
        set.insert(arr[i]);
    }
    return ans >= k;
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> k;
    arr.resize(n);
    for (int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        arr[i] = {x, y};
    }
    sort(arr.begin(), arr.end(), [](const pll& a, const pll& b){
        return a.f + a.s < b.f + b.s;
    });
    ll low = 0, high = 4e9;
    while (low < high){
        ll mid = (low + high)/2;
        if (check(mid, false)){
            high = mid;
        }else{
            low = mid+1;
        }
    }
    check(low, true);
    assert((int)res.size() >= k);
    sort(res.begin(), res.end());
    for (int i=0; i<k; i++){
        cout << res[i] << "\n";
    }
}

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