#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 = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 230;
ll n, k;
pll a[N];
map<pll,ll>mp;
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();
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();
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 = 1, r = n, 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(auto x : ans) cout << x << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
Compilation message
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:30: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]
30 | while(i < a.size() && j < b.size()){
| ~~^~~~~~~~~~
road_construction.cpp:30: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]
30 | while(i < a.size() && j < b.size()){
| ~~^~~~~~~~~~
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(i < a.size()) res.pb(a[i++]);
| ~~^~~~~~~~~~
road_construction.cpp:35: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]
35 | while(j < b.size()) res.pb(b[j++]);
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7665 ms |
9564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7335 ms |
11104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7335 ms |
11104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
