记录编号	601178	评测结果	AAAAAAAAAA
题目名称	3117.专家系统	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	4.401 s
提交时间	2025-06-03 21:27:03	内存使用	8.46 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
#define max(__a, __b) [&](ll _a, ll _b) {return _a > _b ? _a : _b;} ((__a), (__b))
#define min(__a, __b) [&](ll _a, ll _b) {return _a < _b ? _a : _b;} ((__a), (__b))
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
#define ls(root) root << 1
#define rs(root) root << 1 | 1

template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0) putchar('-'), x = -x;
  static int sta[64], top;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAXN = 1e5 + 10;
const ll INF = 0x7fffffffffffffff;

struct NODE {
  ll maxx, lazy;
} node[MAXN << 2];

void PushUp(int root) {
  node[root].maxx = max(node[ls(root)].maxx, node[rs(root)].maxx);
}

void PushDown(int root, int lt, int rt) {
  if (node[root].lazy) {
    node[ls(root)].maxx += node[root].lazy;
    node[ls(root)].lazy += node[root].lazy;
    node[rs(root)].maxx += node[root].lazy;
    node[rs(root)].lazy += node[root].lazy;
    node[root].lazy = 0;
  }
}

void AddSeq(int root, int lt, int rt, int lq, int rq, int val) {
  if (lt == lq && rt == rq) {
    node[root].maxx += val;
    node[root].lazy += val;
    return ;
  }
  PushDown(root, lt, rt);
  int mid = lt + ((rt - lt) >> 1);
  if (rq <= mid) {
    AddSeq(ls(root), lt, mid, lq, rq, val);
  } else if (lq > mid) {
    AddSeq(rs(root), mid + 1, rt, lq, rq, val);
  } else {
    AddSeq(ls(root), lt, mid, lq, mid, val);
    AddSeq(rs(root), mid + 1, rt, mid + 1, rq, val);
  }
  PushUp(root);
}

struct POINT {
  ll x, y;
} a[MAXN];
ll ysort[MAXN];
ll ydisc[MAXN];
ll ybefore[MAXN];

ll n, k;

bool check(ll s) {
  for (int i = 1; i <= n; ++i) {
    ybefore[i] = ::std::lower_bound(ysort + 1, ysort + n + 1, a[i].y - s) - ysort;
  }
  //printf("s=%d\n", s);
  //printf("yorign : ");
  //for (int i = 1; i <= n; ++i) {
  //  printf("%d%c", a[i].y, " \n"[i == n]);
  //}
  //printf("ysort  : ");
  //for (int i = 1; i <= n; ++i) {
  //  printf("%d%c", ysort[i], " \n"[i == n]);
  //}
  //printf("ydisc  : ");
  //for (int i = 1; i <= n; ++i) {
  //  printf("%d%c", ydisc[i], " \n"[i == n]);
  //}
  //printf("ybefore: ");
  //for (int i = 1; i <= n; ++i) {
  //  printf("%d%c", ybefore[i], " \n"[i == n]);
  //}
  //printf("\n");
  memset(node, 0, sizeof node);
  for (int i = 1, j = 1; i <= n; AddSeq(1, 1, n, ybefore[i], ydisc[i], -1)/*, printf("SegAdd 1, 1, n, %d, %d, -1\n", ybefore[i], ydisc[i])*/, ++i) {
    while (a[i].x + s >= a[j].x && j <= n) AddSeq(1, 1, n, ybefore[j], ydisc[j], 1)/*, printf("SegAdd 1, 1, n, %d, %d, 1\n", ybefore[j], ydisc[j])*/, ++j;
    if (node[1].maxx >= k) return true;
  }
  return false;
}

int main() {
  freopen("expert.in", "r", stdin);
  freopen("expert.out", "w", stdout);
  n = read<ll>(), k = read<ll>();
  ll xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;
  for (int i = 1; i <= n; ++i) {
    a[i].x = read<ll>(), a[i].y = read<ll>();
    xmax = max(xmax, a[i].x);
    xmin = min(xmin, a[i].x);
    ymax = max(ymax, a[i].y);
    ymin = min(ymin, a[i].y);
  }
  ::std::sort(a + 1, a + n + 1, [](POINT x, POINT y) {
    if (x.x != y.x) return x.x < y.x;
    return x.y < y.y;
  });
  for (int i = 1; i <= n; ++i) ysort[i] = a[i].y;
  ::std::sort(ysort + 1, ysort + n + 1);
  for (int i = 1; i <= n; ++i) {
    ydisc[i] = ::std::lower_bound(ysort + 1, ysort + n + 1, a[i].y) - ysort;
  }
  ll l = 1, r = max(xmax - xmin, ymax - ymin), ans = max(xmax - xmin, ymax - ymin);
  //fprintf(stdout, "%lld %lld %lld %lld\n", xmax, xmin, ymax, ymin);
  while (l <= r) {
    ll mid = l + ((r - l) >> 1);
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
      //printf("r = mid - 1\n");
    } else {
      l = mid + 1;
      //printf("l = mid + 1\n");
    }
  }
  write(ans);
  return 0;
}