Submission #1143886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143886		VMaksimoski008	Road Construction (JOI21_road_construction)	C++20	6 / 100	2183 ms	18060 KiB

road_construction

#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = 
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, K;
vector<ar<int, 2> > a;
Tree<pair<ll, ll> > st;
vector<ll> vec;

ll get(ll l, ll r) {
    return st.order_of_key({ r+1, 0 }) - st.order_of_key({ l, 0 });
}

bool f(ll d, bool flag) {
    ll cnt = 0;

    int p = 1;
    st.clear();
    for(int i=1; i<=n; i++) {
        while(p < i && a[i][0] - a[p][0] > d) {
            st.erase({ a[p][1], p });
            p++;
        }
        cnt += get(a[i][1] - d, a[i][1] + d);

        if(flag && get(a[i][1]-d, a[i][1]+d) > 0) {
            auto it = st.lower_bound({ a[i][1]-d, 0 });
            while(it != st.end() && it->first <= a[i][1]+d) {
                ll x = abs(a[i][0] - a[it->second][0]);
                ll y = abs(a[i][1] - it->first);
                vec.push_back(max( x, y ));
                it++;
            }
        }

        st.insert({ a[i][1], i });
    }

    return (cnt >= K);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> K;
    a.push_back({ 0, 0 });
    for(int i=1; i<=n; i++) {
        int x, y; cin >> x >> y;
        a.push_back({ x - y, x + y });
    }
    sort(a.begin()+1, a.begin()+n+1);

    ll l=0, r=4e9, ans=4e9;
    while(l <= r) {
        ll mid = (l + r) / 2;
        if(f(mid, 0)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    f(ans-1, 1);
    while(vec.size() < K) vec.push_back(ans);
    sort(vec.begin(), vec.end());
    for(auto x : vec) 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