// Lights, camera, b*tch smile, even when you wanna die// He said he'd love me all his life// But that life was too short #include <algorithm>#include <iostream>#include <string>#include <vector>typedef long long ll;using namespace std; struct bod { ll x, y; };bool cmpy(bod a, bod b) { return a.y < b.y; }struct sgt2d{ int n; vector<vector<ll> > st, sx; vector<ll> cs; void init(vector<bod> v) { for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x); sort(cs.begin(), cs.end()), cs.erase(unique(cs.begin(), cs.end()), cs.end()); n = cs.size(); st.assign(n * 2, {}), sx.assign(n * 2, {}); sort(v.begin(), v.end(), cmpy); for (bod i : v) { int x = lower_bound(cs.begin(), cs.end(), i.x) - cs.begin(); for (x += n; x > 0; x >>= 1) st[x].push_back(i.y), sx[x].push_back(i.x); } } int query(ll lx, ll rx, ll ly, ll ry) { lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin(); rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin(); int ans = 0; for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1) { if (lx & 1) ans += upper_bound(st[lx].begin(), st[lx].end(), ry) - lower_bound(st[lx].begin(), st[lx].end(), ly), lx++; if (rx & 1) rx--, ans += upper_bound(st[rx].begin(), st[rx].end(), ry) - lower_bound(st[rx].begin(), st[rx].end(), ly); } return ans; } void query2(ll lx, ll rx, ll ly, ll ry, vector<ll> &ans, bod b, ll lim) { lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin(); rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin(); for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1) { if (lx & 1) { int li = lower_bound(st[lx].begin(), st[lx].end(), ly) - st[lx].begin(); int ri = upper_bound(st[lx].begin(), st[lx].end(), ry) - st[lx].begin(); for (int i = li; i < ri; i++) ans.push_back(max(abs(st[lx][i] - b.y), abs(sx[lx][i] - b.x))); lx++; } if (rx & 1) { rx--; int li = lower_bound(st[rx].begin(), st[rx].end(), ly) - st[rx].begin(); int ri = upper_bound(st[rx].begin(), st[rx].end(), ry) - st[rx].begin(); for (int i = li; i < ri; i++) ans.push_back(max(abs(st[rx][i] - b.y), abs(sx[rx][i] - b.x))); } } }};sgt2d st;int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<bod> o(n), v(n); for (int i = 0; i < n; i++) { //o[i].x = rand() * 10000 + rand(), o[i].y = rand() * 10000 + rand(); cin >> o[i].x >> o[i].y; v[i].x = o[i].x + o[i].y; v[i].y = o[i].x - o[i].y; } random_shuffle(v.begin(), v.end()); st.init(v); ll lo = 1, hi = 1e10; while (lo < hi) { ll mi = (lo + hi) / 2; ll cnt = 0; for (int i = 0; i < n; i++) { cnt += st.query(v[i].x - mi, v[i].x +mi, v[i].y - mi, v[i].y + mi)-1; if (cnt >= 2*k) break; } if (cnt >= k) hi = mi; else lo = mi + 1; } vector<ll> ans; for (int i = 0; i < n; i++) { st.query2(v[i].x - lo + 1, v[i].x, v[i].y - lo + 1, v[i].y, ans, v[i], lo - 1); st.query2(v[i].x - lo + 1, v[i].x - 1, v[i].y + 1, v[i].y + lo - 1, ans, v[i], lo - 1); } sort(ans.begin(), ans.end(), greater<ll>()); while (ans.size() && ans.back() == 0) ans.pop_back(); reverse(ans.begin(), ans.end()); while (ans.size() > k) ans.pop_back(); while (ans.size() < k) ans.push_back(lo); for (int i = 0; i < k; i++) cout << ans[i] << "\n"; return 0;}
Compilation message
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status
