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;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 250005;
const int LOG = 18;
int n, k;
int x[MAXN], y[MAXN], sx[MAXN], sy[MAXN], fen[MAXN], ind[MAXN];
vector <llint> sazx, sazy, vx[MAXN], vy[MAXN], sol;
void ubaci (int x, int k) {
for (x++; x < MAXN; x += x&-x) fen[x] += k;
}
int upit (int x) {
int res = 0;
for (x++; x > 0; x -= x&-x) res += fen[x];
return res;
}
int kth (int br) {
int pos = 0;
for (int i = LOG - 1; i >= 0; i--) {
if (pos + (1 << i) < MAXN && br > fen[pos + (1 << i)]) {
pos += 1 << i;
br -= fen[pos];
}
}
return pos;
}
void sazmi () {
for (int i = 1; i <= n; i++) {
sazx.push_back(x[i]);
sazy.push_back(y[i]);
}
sort(sazx.begin(), sazx.end());
sort(sazy.begin(), sazy.end());
sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
for (int i = 1; i <= n; i++) {
sx[i] = lower_bound(sazx.begin(), sazx.end(), x[i]) - sazx.begin();
sy[i] = lower_bound(sazy.begin(), sazy.end(), y[i]) - sazy.begin();
vx[sx[i]].push_back(i);
}
for (int i = 0; i < sazx.size(); i++) {
for (auto j : vx[i]) {
vy[sy[j]].push_back(j);
}
}
}
llint get_dist (int i, int j) {
return max(abs(x[i] - x[j]), abs(y[i] - y[j]));
}
llint calc (llint len, bool flg) {
llint res = 0;
int p = 0;
for (int i = 0; i < sazy.size(); i++) {
ind[i] = 0;
}
for (int i = 0; i < sazx.size(); i++) {
while (p < i && sazx[i] - sazx[p] > len) {
for (auto j : vx[p]) {
ubaci(sy[j], -1);
ind[sy[j]]++;
}
p++;
}
for (auto j : vx[i]) {
int lo = lower_bound(sazy.begin(), sazy.end(), y[j] - len) - sazy.begin();
int hi = upper_bound(sazy.begin(), sazy.end(), y[j] + len) - sazy.begin() - 1;
int br_lo = upit(lo - 1);
int br_hi = upit(hi);
res += br_hi - br_lo;
if (flg == 1) {
vector <int> tmp;
for (int br = br_lo + 1; br <= br_hi; br++) {
tmp.push_back(kth(br));
}
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (auto h : tmp) {
for (int br = ind[h]; br < vy[h].size(); br++) {
int sus = vy[h][br];
if (x[sus] > x[j]) break;
sol.push_back(get_dist(j, sus));
}
}
}
ubaci(sy[j], 1);
}
}
while (p < sazx.size()) {
for (auto j : vx[p]) {
ubaci(sy[j], -1);
}
p++;
}
return res;
}
llint get_len () {
llint lo = 1, hi = 4e9 + 5;
while (lo < hi) {
llint mid = (lo + hi) / 2;
if (calc(mid, 0) >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin >> n >> k;
//n = 250000; k = 250000;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
//x[i] = uniform_int_distribution<int>(-1e9, 1e9)(rng);
//y[i] = uniform_int_distribution<int>(-1e9, 1e9)(rng);
int nx = x[i] - y[i];
int ny = x[i] + y[i];
x[i] = nx; y[i] = ny;
//cout << "bla " << nx << " " << ny << endl;
}
sazmi();
llint len = get_len();
calc(len - 1, 1);
sort(sol.begin(), sol.end());
while (sol.size() < k) sol.push_back(len);
for (auto x : sol) cout << x << '\n';
return 0;
}
Compilation message (stderr)
road_construction.cpp: In function 'void sazmi()':
road_construction.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < sazx.size(); i++) {
| ~~^~~~~~~~~~~~~
road_construction.cpp: In function 'llint calc(llint, bool)':
road_construction.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0; i < sazy.size(); i++) {
| ~~^~~~~~~~~~~~~
road_construction.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < sazx.size(); i++) {
| ~~^~~~~~~~~~~~~
road_construction.cpp:88:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int br = ind[h]; br < vy[h].size(); br++) {
| ~~~^~~~~~~~~~~~~~
road_construction.cpp:98:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | while (p < sazx.size()) {
| ~~^~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:139:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
139 | while (sol.size() < k) sol.push_back(len);
| ~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |