Submission #1243777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243777		Double_Slash	Road Construction (JOI21_road_construction)	C++20	5 / 100	6368 ms	2162688 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

int n, k, x[250000], y[250000];
ll ans;

int main() {
    cin >> n >> k;
    k <<= 1;
    vector<int> cc;
    for (int i = n; i--;) {
        cin >> x[i] >> y[i];
        tie(x[i], y[i]) = pint{x[i] + y[i], x[i] - y[i]};
        cc.emplace_back(x[i]);
    }
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    auto idx = [&] (ll x) {
        if (x <= cc[0]) return 0;
        if (x > cc.back()) return (int) cc.size();
        return (int) (lower_bound(all(cc), x) - cc.begin());
    };
    struct St {
        int n;
        vector<int> st;

        St(int n) : n(n), st(n << 1) {}

        void upd(int i, int v) {
            for (i += n; i; i >>= 1) st[i] += v;
        }

        int operator()(int l, int r) {
            int ret = 0;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if (l & 1) ret += st[l++];
                if (r & 1) ret += st[--r];
            }
            return ret;
        }
    } st{(int) cc.size()};
    vector<array<ll, 3>> v;
    v.reserve(n * 3);
    for (int K = 32; K--;) {
        ans += 1ll << K;
        for (int i = n; i--;) {
            v.push_back({y[i] - ans, -1, i});
            v.push_back({y[i], 0, i});
            v.push_back({y[i] + ans, 1, i});
        }
        sort(all(v));
        ll cnt = -n;
        st.st.clear();
        for (auto &[yi, a, i]: v) {
            if (a) cnt += a * st(idx(x[i] - ans), idx(x[i] + ans + 1));
            else st.upd(idx(x[i]), 1);
        }
        v.clear();
        if (cnt > k) ans -= 1 << K;
    }
    struct St2 {
        int n;
        vector<vector<int>> st;

        St2(int n) : n(n), st(n << 1) {}

        void upd(int i, int j) {
            for (i += n; i; i >>= 1) st[i].emplace_back(j);
        }

        void operator()(int l, int r, int j, vector<ll> &v) {
            auto add = [&] (vector<int> &a) {
                for (int i = a.size(); i-- and y[a[i]] >= y[j] - ans;) {
                    if (a[i] != j) v.emplace_back(max(abs((ll) x[a[i]] - x[j]), abs((ll) y[a[i]] - y[j])));
                }
            };
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if (l & 1) add(st[l++]);
                if (r & 1) add(st[--r]);
            }
        }
    } st2{(int) cc.size()};
    for (int i = n; i--;) {
        v.push_back({y[i], 0, i});
        v.push_back({y[i] + ans, 1, i});
    }
    sort(all(v));
    vector<ll> dists;
    dists.reserve(k);
    for (auto &[yi, a, i]: v) {
        if (a) st2(idx(x[i] - ans), idx(x[i] + ans + 1), i, dists);
        else st2.upd(idx(x[i]), i);
    }
    sort(all(dists));
    while (dists.size() < k) dists.emplace_back(ans + 1);
    for (int i = 0; i < k; i += 2) cout << dists[i] << endl;
}

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