Submission #705792

#	Time	Username	Problem	Language	Result	Execution time	Memory
705792		bebra	Road Construction (JOI21_road_construction)	C++17	100 / 100	2320 ms	15972 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

#define dbg(x) cerr << #x << ": " << x << endl;


struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(n);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] += value;
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
            res += tree[i];
        }
        for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res -= tree[i];
        }
        return res;
    }
};


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

    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> points(n);
    vector<int> coords;
    for (auto& [x, y] : points) {
        cin >> x >> y;
        int x0 = x;
        int y0 = y;
        x = x0 + y0;
        y = x0 - y0;
        coords.push_back(y);
    }

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

    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
    for (auto& [x, y] : points) {
        y = lower_bound(coords.begin(), coords.end(), y) - coords.begin();
    }

    auto check = [&](ll dist) {
        FenwickTree tree(coords.size());
        int res = 0;
        int p = 0;
        for (int i = 0; i < n; ++i) {
            while (points[i].first - points[p].first > dist) {
                tree.update(points[p].second, -1);
                ++p;
            }
            int l = lower_bound(coords.begin(), coords.end(), coords[points[i].second] - dist) - coords.begin();
            int r = upper_bound(coords.begin(), coords.end(), coords[points[i].second] + dist) - coords.begin() - 1;
            res += tree.query(l, r);
            tree.update(points[i].second, 1);
            if (res >= k) return true;
        }
        return res >= k;
    };

    ll dist;
    {
        ll l = -1;
        ll r = 4e9 + 1;
        while (l != r - 1) {
            ll m = (l + r) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        dist = l;
    }

    vector<ll> ans;
    ans.reserve(k);

    set<pair<ll, int>> s;
    int p = 0;
    for (int i = 0; i < n; ++i) {
        while (points[i].first - points[p].first > dist) {
            s.erase({coords[points[p].second], p});
            ++p;
        }
        auto it = s.lower_bound({coords[points[i].second] - dist, -1});
        while (it != s.end() && it->first <= coords[points[i].second] + dist) {
            int j = it->second;
            ll curr_dist = max(abs(points[i].first - points[j].first), abs(coords[points[i].second] - coords[points[j].second]));
            ans.push_back(curr_dist);
            ++it;
        }
        s.emplace(coords[points[i].second], i);
    }

    while ((int)ans.size() < k) {
        ans.push_back(dist + 1);
    }
    sort(ans.begin(), ans.end());

    for (auto x : ans) {
        cout << x << '\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