Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- const int N = 200200;
- using namespace std;
- int n;
- int id[N];
- int t[N];
- pair < int, int > a[N];
- vector < pair < int, int > > v;
- void upd(int x, int g)
- {
- while(x < N){
- t[x] += g;
- x += x & -x;
- }
- }
- int get_c(int x)
- {
- int res = 0;
- while(x > 0){
- res += t[x];
- x -= x & -x;
- }
- return res;
- }
- long long get(int D)
- {
- long long res = 0;
- for(int i = 0; i < N; i++) t[i] = 0;
- for(int i = 1, j = 1; i <= n; i++){
- if(i > 1){
- upd(id[i - 1], 1);
- }
- while(j < i && a[i].fi - a[j].fi > D){
- upd(id[j], -1);
- j += 1;
- }
- int l = lower_bound(v.begin(), v.end(), make_pair(a[i].se - D, 0)) - v.begin();
- int r = lower_bound(v.begin(), v.end(), make_pair(a[i].se + D + 1, 0)) - v.begin() - 1;
- if(l <= r){
- res += get_c(v[r].se) - get_c(v[l].se - 1);
- }
- }
- return res;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- long long k;
- cin >> n >> k;
- for(int i = 1; i <= n; i++){
- int x, y;
- cin >> x >> y;
- a[i] = {x + y, x - y};
- }
- sort(a + 1, a + n + 1);
- v.push_back({-2e9, 0});
- v.push_back({2e9, 0});
- for(int i = 1; i <= n; i++){
- v.push_back({a[i].se, i});
- }
- sort(v.begin(), v.end());
- for(int i = 0, j = 0; i < v.size(); i++){
- if(i > 0 && v[i].fi > v[i - 1].fi){
- j += 1;
- }
- id[v[i].se] = j;
- v[i].se = j;
- }
- int l = 1, r = 5e8;
- while(l < r){
- int m = (l + r) / 2;
- if(get(m) >= k){
- r = m;
- } else{
- l = m + 1;
- }
- }
- cout << l << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement