| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 554754 | MilosMilutinovic | Road Construction (JOI21_road_construction) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> x(n);
vector<int> y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
auto Count = [&](long long d) {
vector<tuple<long long, int, long long, long long>> ev;
vector<long long> xs;
for (int i = 0; i < n; i++) {
long long dx = x[i] + y[i];
long long dy = x[i] - y[i];
ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
ev.emplace_back(dx, 2, dy, dy);
xs.push_back(dy - d - 1);
xs.push_back(dy + d);
xs.push_back(dy);
}
sort(ev.begin(), ev.end());
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int sz = xs.size();
fenwick<int> fenw(sz);
long long cnt = 0;
for (auto& e : ev) {
int t = get<1>(e);
if (t == 0) {
int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
cnt -= fenw.get(R) - fenw.get(L);
} else if (t == 1) {
int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
cnt += fenw.get(R) - fenw.get(L);
} else {
int aa = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
fenw.modify(aa, +1);
}
}
if (d == 4) {
cout << cnt << '\n';
}
return (cnt - n) / 2;
};
long long low = 0, high = 4.1e9;
while (low + 1 < high) {
long long mid = (low + high + 1) >> 1;
if (Count(mid) >= k) {
high = mid;
} else {
low = mid;
}
}
cout << high << '\n';
return 0;
}