| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 945998 | itslq | 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>
#include <unordered_map>
using namespace std;
#define int long long
int N, K, X, Y;
vector<int> x(3e5), y(3e5);
unordered_map<int, unordered_map<int, int>> fenwick;
void update(int i, int j1, bool b) {
for (; i <= X; i += i & -i) {
for (int j = j1; j <= Y; j += j & -j) {
if (b) fenwick[i][j]++;
else fenwick[i][j]--;
}
}
}
int query(int i, int j1) {
int S = 0;
for (; i > 0; i -= i & -i) {
for (int j = j1; j > 0; j -= j & -j) {
S += fenwick[i][j];
}
}
return S;
}
bool check(int d) {
int x1, y1, S = 0, ia, ib, ic, id;
vector<int> xdisc, ydisc;
for (int i = 0; i < N; i++) {
x1 = x[i];
y1 = y[i];
xdisc.push_back(x1 - y1 - d);
xdisc.push_back(x1 - y1);
xdisc.push_back(x1 - y1 + d);
ydisc.push_back(x1 + y1 - d);
ydisc.push_back(x1 + y1);
ydisc.push_back(x1 + y1 + d);
}
sort(xdisc.begin(), xdisc.end());
sort(ydisc.begin(), ydisc.end());
xdisc.erase(unique(xdisc.begin(), xdisc.end()), xdisc.end());
ydisc.erase(unique(ydisc.begin(), ydisc.end()), ydisc.end());
X = xdisc.size();
Y = ydisc.size();
fenwick = map<int, map<int, int>>();
for (int i = 0; i < N; i++) {
x1 = x[i];
y1 = y[i];
ia = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1) - xdisc.begin() + 1;
ib = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1) - ydisc.begin() + 1;
if ((S += query(ia, ib)) >= K) return true;
ia = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1 - d) - xdisc.begin() + 1;
ib = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1 + d) - xdisc.begin() + 1;
ic = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1 - d) - ydisc.begin() + 1;
id = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1 + d) - ydisc.begin() + 1;
update(ia, ic, 1);
update(ib + 1, ic, 0);
update(ia, id + 1, 0);
update(ib + 1, id + 1, 1);
}
return false;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
x.resize(N);
y.resize(N);
for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
int l = 0, r = 4e9, m, ans;
while (l <= r) {
m = (l + r) >> 1;
if (check(m)) {
ans = m;
r = --m;
} else {
l = ++m;
}
}
cout << ans;
return 0;
}