Submission #553120

#	Time	Username	Problem	Language	Result	Execution time	Memory
553120		jesus_coconut	Road Construction (JOI21_road_construction)	C++17	100 / 100	2542 ms	13572 KiB

road_construction

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)

using namespace std;
using namespace __gnu_pbds;
using ll = long long;

using pii = pair<ll, ll>;

using oset = tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;


int n, k;
vector<pii> v;

oset s;

void add(int t) {
    s.insert({v[t].S, t});
}

void rm(int t) {
    s.erase({v[t].S, t});
}

ll cnt(ll y, ll dist) {
    return s.order_of_key({y + dist, INT_MAX}) - s.order_of_key({y - dist, INT_MIN});
}

void load() {
    cin >> n >> k;
    v.resize(n);
    for (auto &[a, b] : v) {
        ll ta, tb;
        cin >> ta >> tb;
        a = ta - tb;
        b = ta + tb;
    }
    sort(all(v));
}

ll solve(ll dist) {
    s.clear();
    int prev = 0;
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        while (prev < n && v[prev].F < v[i].F - dist) {
            rm(prev++);
        }
        ret += cnt(v[i].S, dist);
        if (ret >= k) return ret;
        add(i);
    }
    return ret;
}

vector<ll> ans;

void construct(ll dist) {
    set<pair<ll, int>> s;
    int prev = 0;
    for (int i = 0; i < n; ++i) {
        while (prev < n && v[prev].F < v[i].F - dist) {
            s.erase({v[prev].S, prev});
            prev++;
        }
        for (auto it = s.lower_bound({v[i].S - dist, INT_MIN}); it != s.upper_bound({v[i].S + dist, INT_MAX}); ++it) {
            ans.push_back(max(abs(v[i].F - v[it->S].F), abs(v[i].S - v[it->S].S)));
        }
        s.insert({v[i].S, i});
    }
}


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

    load();
    ll lo = 1, hi = 4ll * 1e9 + 100;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (solve(mid) < k) {
            lo = mid + 1;
        } else hi = mid;
    }
    construct(lo - 1);
    sort(all(ans));
    ans.resize(k, lo);
    for (auto a : ans) cout << a << '\n';


    return 0;
}

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