Submission #641526

#	Time	Username	Problem	Language	Result	Execution time	Memory
641526		skittles1412	Road Construction (JOI21_road_construction)	C++17	100 / 100	2525 ms	13580 KiB

road_construction

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

namespace __gnu_pbds {
template <typename T, typename U = less<T>>
using ost =
    tree<T, null_type, U, rb_tree_tag, tree_order_statistics_node_update>;
}

using __gnu_pbds::ost;

void solve() {
    int n, kv;
    cin >> n >> kv;
    pair<long, long> arr[n];
    for (auto& [x, y] : arr) {
        long cx, cy;
        cin >> cx >> cy;
        x = cx + cy;
        y = cx - cy;
    }
    sort(arr, arr + n);
    auto check = [&](long cv) -> bool {
        int cans = 0;
        queue<pair<long, int>> q;
        ost<pair<long, int>> s;
        for (int i = 0; i < n; i++) {
            auto& [x, y] = arr[i];
            while (sz(q) && q.front().first < x - cv) {
                int j = q.front().second;
                s.erase({arr[j].second, j});
                q.pop();
            }
            cans += int(s.order_of_key({y + cv + 1, -1}) -
                        s.order_of_key({y - cv, -1}));
            if (cans >= kv) {
                return false;
            }
            s.insert({y, i});
            q.emplace(x, i);
        }
        return true;
    };
    long l = 0, r = 1e10;
    while (l < r) {
        long mid = (l + r + 1) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    vector<long> ans;
    queue<pair<long, int>> q;
    set<pair<long, int>> s;
    for (int i = 0; i < n; i++) {
        auto& [x, y] = arr[i];
        while (sz(q) && q.front().first < x - l) {
            int j = q.front().second;
            s.erase({arr[j].second, j});
            q.pop();
        }
        for (auto it = s.lower_bound({y - l, -1}),
                  end = s.lower_bound({y + l + 1, -1});
             it != end; ++it) {
            auto& [y1, j] = *it;
            ans.push_back(max(abs(x - arr[j].first), abs(y - y1)));
        }
        s.insert({y, i});
        q.emplace(x, i);
    }
    ans.resize(kv, l + 1);
    sort(begin(ans), end(ans));
    for (auto& a : ans) {
        cout << a << endl;
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}

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