// author: erray
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
const long long inf = (long long) 1e10;
using T = pair<long long, int>;
struct SegTree {
vector<T> tree;
int n;
SegTree(int _n) : n(_n) {
tree.resize(n << 1, pair{-inf, -1});
}
T get(int l, int r) {
T res = {-inf, -1};
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
res = max(res, tree[l++]);
}
if (r & 1) {
res = max(res, tree[--r]);
}
}
return res;
}
void modify(int p, long long x) {
p += n;
tree[p] = {x, p - n};
while (p > 1) {
tree[p >> 1] = max(tree[p], tree[p ^ 1]);
p >>= 1;
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<array<int, 2>> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i][0] >> A[i][1];
}
sort(A.begin(), A.end());
vector<int> ys(N);
for (int i = 0; i < N; ++i) {
ys[i] = A[i][1];
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
int s = int(ys.size());
vector<int> c(N);
for (int i = 0; i < N; ++i) {
c[i] = int(lower_bound(ys.begin(), ys.end(), A[i][1]) - ys.begin());
}
auto Get = [&](long long lim) -> vector<long long> {
debug(lim);
vector<long long> res;
bool reversed = false;
auto Solve = [&] {
SegTree st(s);
vector<priority_queue<long long>> pqs(s);
for (int i = 0; i < N; ++i) {
auto[cx, cy] = A[i];
int cs = c[i];
vector<pair<int, long long>> rb;
int me = cx + cy;
while (true) {
int g = cs - reversed;
auto[x, ind] = st.get(0, max(0, g));
if (g < 0 || x == -inf || 0LL + me - x > lim) {
break;
}
assert(pqs[ind].top() == x);
pqs[ind].pop();
res.push_back(0LL + me - x);
if (int(res.size()) > K) {
debug("end", lim);
return;
}
rb.push_back({ind, x});
long long nw = (pqs[ind].empty() ? -inf : (long long) pqs[ind].top());
st.modify(ind, nw);
}
for (auto[x, b] : rb) {
pqs[x].push(b);
st.modify(x, pqs[x].top());
}
pqs[cs].push(me);
st.modify(cs, pqs[cs].top());
}
};
auto Reverse = [&] {
reversed ^= 1;
for (int i = 0; i < N; ++i) {
c[i] = s - 1 - c[i];
A[i][1] = -A[i][1];
}
};
Solve();
Reverse();
Solve();
return res;
};
long long low = 0, high = (long long) 4e9;
while (low < high) {
long long mid = 1 + ((low + high) >> 1);
debug(mid, Get(mid));
if (int(Get(mid).size()) <= K) {
low = mid;
} else {
high = mid - 1;
}
}
debug(low);
auto ans = Get(low);
sort(ans.begin(), ans.end());
for (int i = 0; i < K; ++i) {
cout << (i < int(ans.size()) ? ans[i] : low + 1) << '\n';
}
}
Compilation message
road_construction.cpp: In constructor 'SegTree::SegTree(int)':
road_construction.cpp:20:29: error: missing template arguments before '{' token
20 | tree.resize(n << 1, pair{-inf, -1});
| ^
road_construction.cpp: In lambda function:
road_construction.cpp:77:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto[cx, cy] = A[i];
| ^
road_construction.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | auto[x, ind] = st.get(0, max(0, g));
| ^
road_construction.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
99 | for (auto[x, b] : rb) {
| ^
