#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; #define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false) #define all(a) a.begin(), a.end() #define F first #define S second #define ll long long #define pii pair<ll, ll> #define ppp pair<ll, pii> #define dout cout << fixed << setprecision(15) #define mid ((l + r) / 2) #define lc (2 * id) #define rc (lc + 1) mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); const ll maxn = 25e4 + 10, maxm = 3e3 + 10, oo = 1e18, lg = 31, sq = 1400, mod = 2e9; int n; ll k; vector<ll> cmp; vector<int> v[maxn]; pii a[maxn]; ppp b[maxn]; int fen[maxn]; int id(ll x){ return lower_bound(all(cmp), x) - cmp.begin(); } int gi[maxn]; void add(int i, int val){ for (; i <= n; i += i & -i) fen[i] += val; } int get(int i){ int res = 0; for (; i > 0; i -= i & -i) res += fen[i]; return res; } ll check(ll x){ int j = 1; ll res = 0; for (int i = 1; i <= n; i++) fen[i] = 0; for (int i = 1; i <= n; i++) { while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > x) { add(gi[j], -1); j++; } res += get(id(a[i].S - a[i].F + x + 1) - 1) - get(id(a[i].S - a[i].F - x) - 1); add(gi[i], 1); } return res; } int p[2][maxn]; void solve() { cin >> n >> k; for (int i = 1; i <= n;i++) cin >> a[i].F >> a[i].S; if(k > 100000) cout << 1 / 0; /*n = 250000; k = n; for (int i = 1; i <= n;i++) a[i].F = rng() % mod; for (int i = 1; i <= n;i++) a[i].S = rng() % mod;*/ for (int i = 1; i <= n;i++) b[i] = {a[i].F + a[i].S, a[i]}; sort(b + 1, b + n + 1); for (int i = 1; i <= n;i++) a[i] = b[i].S; for (int i = 1; i <= n;i++) cmp.push_back(a[i].S - a[i].F); cmp.push_back(-oo); sort(all(cmp)); cmp.resize(unique(all(cmp)) - cmp.begin()); for (int i = 1; i <= n;i++) v[gi[i] = id(a[i].S - a[i].F)].push_back(i); ll l = 1, r = 2 * mod; while(r - l > 1) if(check(mid) >= k) r = mid; else l = mid; vector<ll> ans; for (ll i = 1; i <= k - check(l);i++) ans.push_back(r); int j = 1; for (int i = 1; i <= n; i++) { while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l) { p[0][gi[j]]++; j++; } int fm = id(a[i].S - a[i].F - l); int to = id(a[i].S - a[i].F + l + 1) - 1; for (int o = fm; o <= to; o++) for (int ii = p[0][o]; ii < p[1][o];ii++) ans.push_back(abs(a[i].F - a[v[o][ii]].F) + abs(a[i].S - a[v[o][ii]].S)); p[1][gi[i]]++; } sort(all(ans)); for(auto i : ans) cout << i << "\n"; } signed main() { threesum; int t = 1; //cin >> t; while(t--) solve(); }

road_construction.cpp: In function 'void solve()':
road_construction.cpp:87:19: warning: division by zero [-Wdiv-by-zero]
   87 |         cout << 1 / 0;
      |                 ~~^~~