| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387741 | abc864197532 | Road Construction (JOI21_road_construction) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
for (auto i : x) cout << i << ' ';\
cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300001, K = 111;
struct Pt {
lli x, y, idx;
Pt (lli _x = 0, lli _y = 0) : x(_x), y(_y) {}
bool operator < (const Pt &o) {
return x < o.x;
}
};
struct cmp {
bool operator () (Pt a, Pt b) {
if (a.y == b.y) return a.idx < b.idx;
return a.y < b.y;
}
};
int bit[N];
void reset() {
for (int i = 0; i < N; ++i) bit[i] = 0;
}
void add(int p, int v) {
for (int i = p; i < N; i += i & (-i)) bit[i] += v;
}
int query(int p) {
int ans = 0;
for (int i = p; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector <Pt> a;
for (int i = 0, x, y; i < n; ++i) {
cin >> x >> y;
a.pb(Pt(x + y, x - y));
a.back().idx = i;
}
vector <lli> y_idx;
for (int i = 0; i < n; ++i) y_idx.pb(a[i].y);
sort(all(y_idx));
y_idx.resize(unique(all(y_idx)) - y_idx.begin());
auto get = [&](lli x) {
return lower_bound(all(y_idx), x) - y_idx.begin() + 5;
};
sort(all(a));
auto chk = [&](lli d) {
/*
* 2 4 8 9 15
* 4 9
*/
reset();
lli ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && a[j].x + d < a[i].x) add(get(a[j++].y), -1);
ans += query(get(a[i].y + d + 1) - 1) - query(get(a[i].y - d) - 1);
add(get(a[i].y), 1);
}
return ans;
};
lli l = 0, r = 2e9 + 87;
while (r - l > 1) {
((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
}
int d = l;
l = 0, r = 2e9 + 87;
while (r - l > 1) {
((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
}
vector <int> ans;
set <Pt, cmp> s;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && a[j].x + d < a[i].x) s.erase(a[j++]);
for (auto it = s.lower_bound(Pt(0, a[i].y - d)); it != s.end() && it->y <= a[i].y + d; ++it) {
ans.pb(max(a[i].x - it->x, abs(it->y - a[i].y)));
}
s.insert(a[i]);
}
sort(all(ans));
for (int i = 0; i < k; ++i) {
if (i < ans.size()) cout << ans[i] << '\n';
else cout << r << '\n';
}
}