KDT 被卡了，但是正常的 KDT 应该能过除 #13 外所有点

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define fork for(int k = 0; k < K; k++)
#define ll long long

using namespace std;

int read()
{
	int x = 0, f = 1;
	char ch = 0;
	while(!isdigit(ch))
	{
		if(ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

const int N = 100000, K = 2, INF = (int)0x3f3f3f3f3f3f3f3f;
int n, m;

struct Node
{
	int x[K];
}node[N + 5];
Node Mn(Node x, Node y)
{
	for(int k = 0; k < K; k++)
	{
		x.x[k] = min(x.x[k], y.x[k]);
	}
	return x;
}
Node Mx(Node x, Node y)
{
	for(int k = 0; k < K; k++)
	{
		x.x[k] = max(x.x[k], y.x[k]);
	}
	return x;
}
ll dis(Node x, Node y)
{
	ll ret = 0;
	for(int k = 0; k < K; k++)
	{
		ret += ((ll)x.x[k] - y.x[k]) * ((ll)x.x[k] - y.x[k]);
	}
	return ret;
}

void init()
{
	n = read(), m = read();
//	m = (m + 1) >> 1;
	for(int i = 1; i <= n; i++)
	{
		fork
		{
			node[i].x[k] = read();
		}
	}
}

int b[N + 5];
struct Tr
{
	int id;
	int lx, rx;
	Node mn, mx;
	ll gdis(Node t)
	{
		ll ret = 0;
		for(int k = 0; k < K; k++)
		{
			ret += max(((ll)t.x[k] - mn.x[k]) * ((ll)t.x[k] - mn.x[k]), ((ll)t.x[k] - mx.x[k]) * ((ll)t.x[k] - mx.x[k]));
		}
		return ret;
	}
}tr[N + 5];
int rt;
int cntn;
void pushup(int x)
{
	tr[x].mn = tr[x].mx = node[tr[x].id];
	if(tr[x].lx)
	{
		tr[x].mn = Mn(tr[x].mn, tr[tr[x].lx].mn);
	}
	if(tr[x].rx)
	{
		tr[x].mn = Mn(tr[x].mn, tr[tr[x].rx].mn);
	}
	if(tr[x].lx)
	{
		tr[x].mx = Mx(tr[x].mx, tr[tr[x].lx].mx);
	}
	if(tr[x].rx)
	{
		tr[x].mx = Mx(tr[x].mx, tr[tr[x].rx].mx);
	}
}
void build(int &x, int l, int r, int kd)
{
	if(l > r)
	{
		return;
	}
	if(x == 0)
	{
		x = ++cntn;
	}
	nth_element(b + l, b + mid, b + r, [kd](int aa, int bb){return node[aa].x[kd] < node[bb].x[kd];});
	tr[x].id = b[mid];
//	printf("%lld %lld 1111\n", x, tr[x].id);
	build(tr[x].lx, l, mid - 1, (kd + 1) % K);
	build(tr[x].rx, mid + 1, r, (kd + 1) % K);
	pushup(x);
}
struct Dat
{
	ll dis;
	int id;
	bool operator < (const Dat &t) const
	{
		return t.dis < dis;
	}
};
priority_queue <Dat> qu;
void ask(int x, Node t, int k)
{
	if(x == 0)
	{
		return;
	}
	if((int)qu.size() < k || dis(node[tr[x].id], t) > qu.top().dis)
	{
		qu.push({dis(node[tr[x].id], t), tr[x].id});
		if((int)qu.size() > k)
		{
			qu.pop();
		}		
	}
	ll gl = -1, gr = -1;
	if(tr[x].lx)
	{
		gl = tr[tr[x].lx].gdis(t);
	}
	if(tr[x].rx)
	{
		gr = tr[tr[x].rx].gdis(t);
	}
//	if(x == 1)
//	{
//		printf("%f %f 114\n", gl, gr);
//	}
	if(gl > gr)
	{
		if((int)qu.size() < k || ((int)qu.size() == k && gl > qu.top().dis))
		{
			ask(tr[x].lx, t, k);
		}
		if((int)qu.size() < k || ((int)qu.size() == k && gr > qu.top().dis))
		{
			ask(tr[x].rx, t, k);
		}
	}
	else
	{
		if((int)qu.size() < k || ((int)qu.size() == k && gr > qu.top().dis))
		{
			ask(tr[x].rx, t, k);
		}		
		if((int)qu.size() < k || ((int)qu.size() == k && gl > qu.top().dis))
		{
			ask(tr[x].lx, t, k);
		}
	}
}

priority_queue <Dat> ans;
void solve()
{
	for(int i = 1; i <= n; i++)
	{
		b[i] = i;
	}
	build(rt, 1, n, 0);
	for(int i = 1; i <= n; i++)
	{
		ask(rt, node[i], min(m, n));
		while(qu.size())
		{
			ans.push(qu.top());
			if((int)ans.size() > m * 2)
			{
				ans.pop();
			}
			qu.pop();
		}
	}
	printf("%lld", ans.top().dis);
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	init();
	solve();
	return 0;
}