#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 int long long #define pii pair<ll, ll> #define ppp pair<ll, pii> #define dout cout << fixed << setprecision(15) #define mid ((l + r) >> 1) #define lc (id << 1) #define rc (lc + 1) mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); const ll maxn = 1e6 + 10, maxm = 3e3 + 10, oo = 1e18, lg = 31, sq = 1400, mod = 2e9; int n; ll k; vector<ll> cmp; queue<int> q[maxn]; pii a[maxn]; ppp b[maxn]; int fen[maxn]; inline int id(ll x){ return lower_bound(all(cmp), x) - cmp.begin(); } int gi[maxn]; inline void add(int i, int val){ for (; i <= n; i += i & -i) fen[i] += val; } inline int get(int l, int r){ int res = 0; for (; r > 0; r -= r & -r) res += fen[r]; for (; l > 0; l -= l & -l) res -= fen[l]; return res; } ll check(ll x){ int j = 1; ll res = 0; fill(fen + 1, fen + n + 1, 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, id(a[i].S - a[i].F + x + 1) - 1); add(gi[i], 1); } return res; } void solve() { cin >> n >> k; for (int i = 1; i <= n;i++) cin >> a[i].F >> a[i].S; /*if(k < 20000) 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++) gi[i] = id(a[i].S - a[i].F); ll l = 0, 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); if(check(l) >= k) cout << 1 / 0; int j = 1; for (int i = 1; i <= n; i++) { while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l) { q[gi[j]].pop(); 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++){ int sz = q[o].size(); for (int ii = 0; ii < sz; ii++) { ans.push_back(abs(a[i].F - a[q[o].front()].F) + abs(a[i].S - a[q[o].front()].S)); q[o].push(q[o].front()); q[o].pop(); } } q[gi[i]].push(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:131:19: warning: division by zero [-Wdiv-by-zero]
  131 |         cout << 1 / 0;
      |                 ~~^~~