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 ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 230;
ll n, k;
pll a[N];
vector<ll>ans;
struct segment_tree{
ll n;
vector<vector<pll>>st;
void init(ll _n){
n = _n;
st.resize(4 * n + 10);
build(1,1,n);
}
vector<pll>merge(const vector<pll>&a, const vector<pll>&b){
ll i = 0, j = 0;
vector<pll>res;
while(i < a.size() && j < b.size()){
if(a[i].F <= b[j].F) res.pb(a[i++]);
else res.pb(b[j++]);
}
while(i < a.size()) res.pb(a[i++]);
while(j < b.size()) res.pb(b[j++]);
return res;
}
void build(ll id, ll l, ll r){
if(l == r){
st[id].pb({a[l].S, l});
return;
}
ll mid = (l + r) / 2;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] = merge(st[2 * id], st[2 * id + 1]);
}
ll get(ll id, ll l, ll r, ll left, ll right, ll L, ll R){
if(l > right || r < left) return 0;
if(left <= l && r <= right){
ll i = upper_bound(all(st[id]), make_pair(R, inf)) - st[id].begin() - 1;
ll j = lower_bound(all(st[id]), make_pair(L, -inf)) - st[id].begin();
if(j >= (ll)st[id].size()) return 0;
return i - j + 1;
}
ll mid = (l + r) / 2;
return (get(2 * id, l, mid, left, right, L, R) + get(2 * id + 1, mid + 1, r, left, right, L, R));
}
void get_order(ll id, ll l, ll r, ll left, ll right, ll L, ll R, ll idx){
if(l > right || r < left) return;
if(left <= l && r <= right){
ll i = upper_bound(all(st[id]), make_pair(R, inf)) - st[id].begin() - 1;
ll j = lower_bound(all(st[id]), make_pair(L, -inf)) - st[id].begin();
if(j >= (ll)st[id].size()) return;
for(int x = j; x <= i;x++){
ll cur = st[id][x].S;
ans.pb(max(abs(a[cur].F - a[idx].F), abs(a[cur].S - a[idx].S)));
}
return;
}
ll mid = (l + r) / 2;
get_order(2 * id, l, mid, left, right, L, R, idx);
get_order(2 * id + 1, mid + 1, r, left, right, L, R, idx);
}
ll get(ll l, ll r, ll L, ll R){return get(1,1,n,l,r,L,R);}
} st;
bool check(ll val){
ll j = 1, cnt = 0;
for(int i = 1; i <= n;i++){
while(j < i && a[i].F - a[j].F > val) j++;
if(j < i) cnt += st.get(j, i - 1, a[i].S - val, a[i].S + val);
}
return cnt >= k;
}
void add_order(ll val){
ll j = 1;
for(int i = 1; i <= n;i++){
while(j < i && a[i].F - a[j].F > val) j++;
if(j < i) {
st.get_order(1,1,n,j, i - 1, a[i].S - val, a[i].S + val, i);
}
}
}
void to_thic_cau(){
cin >> n >> k;
for(int i = 1; i <= n;i++){
ll x,y; cin >> x >> y;
a[i].F = x - y, a[i].S = x + y;
}
sort(a + 1, a + n + 1);
st.init(n);
ll l = 0, r = 5e9, res = -1;
while(l <= r){
ll mid = (l + r) / 2;
if(check(mid)) res = mid, r = mid - 1;
else l = mid + 1;
}
add_order(res);
sort(all(ans));
for(int i = 0; i < k;i++) cout << ans[i] << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
Compilation message (stderr)
road_construction.cpp: In member function 'std::vector<std::pair<long long int, long long int> > segment_tree::merge(const std::vector<std::pair<long long int, long long int> >&, const std::vector<std::pair<long long int, long long int> >&)':
road_construction.cpp:29:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(i < a.size() && j < b.size()){
| ~~^~~~~~~~~~
road_construction.cpp:29:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(i < a.size() && j < b.size()){
| ~~^~~~~~~~~~
road_construction.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(i < a.size()) res.pb(a[i++]);
| ~~^~~~~~~~~~
road_construction.cpp:34:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(j < b.size()) res.pb(b[j++]);
| ~~^~~~~~~~~~
# | 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... |