Submission #424477

#	Time	Username	Problem	Language	Result	Execution time	Memory
424477		Namnamseo	Road Construction (JOI21_road_construction)	C++17	0 / 100	10035 ms	89160 KiB

road_construction

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define rrep(i, n) for (int i=1; i<=(n); ++i)
#define all(v) ((v).begin()), ((v).end())
#define x first
#define y second
using namespace std; using ll=long long; using pll=pair<ll,ll>;
const int maxn = 250'000 + 10;

int n, k;
pll p[maxn];
int xv[maxn], xvn;
int yv[maxn], yvn;
int xi[maxn], yi[maxn];

void In() {
	cin.tie(0)->sync_with_stdio(0); cin >> n >> k; rep(i, n) cin >> p[i].x >> p[i].y;
	rep(i, n) { auto [x, y] = p[i]; p[i] = {x+y, x-y}; }
	sort(p, p+n);
}

void Cc() {
	rep(i, n) xv[i] = p[i].x; sort(xv, xv+n); xvn = unique(xv, xv+n) - xv; rep(i, n) xi[i] = lower_bound(xv, xv+xvn, p[i].x) - xv;
	rep(i, n) yv[i] = p[i].y; sort(yv, yv+n); yvn = unique(yv, yv+n) - yv; rep(i, n) yi[i] = lower_bound(yv, yv+yvn, p[i].y) - yv;
}

const int M = 262144;

struct Pst {
	struct {
		int pl, pr, val;
	} node[2*M + maxn * 19];
	int nn;

	int init(int l=0, int r=xvn-1) {
		int me = ++nn;
		if (l != r) {
			int mid = (l+r)/2;
			node[me].pl = init(l, mid);
			node[me].pr = init(mid+1, r);
		}
		return me;
	}

	int upd(int orig, int up, int l=0, int r=xvn-1) {
		if (r < up || up < l) return orig;
		int me = ++nn;
		if (l == r) { node[me].val = node[orig].val + 1; return me; }
		int mid = (l+r)/2;
		node[me] = node[orig];
		node[me].val++;
		if (up <= mid) node[me].pl = upd(node[orig].pl, up, l, mid);
		else node[me].pr = upd(node[orig].pr, up, mid+1, r);
		return me;
	}

	int rsum(int nd, int ql, int qr, int l=0, int r=xvn-1) {
		if (qr < l || r < ql) return 0;
		if (ql <= l && r <= qr) return node[nd].val;
		int mid = (l+r)/2;
		return rsum(node[nd].pl, ql, qr, l, mid) +
			   rsum(node[nd].pr, ql, qr, mid+1, r);
	}
} pst;

int roots[maxn];

vector<int> t[M<<1];

bool ycomp(const int& a, const int& b) { return p[a].y < p[b].y; }

void Bt() {
	// pst
	{
		roots[0] = pst.init();
		int cr = roots[0];
		rep(i, n) {
			cr = pst.upd(cr, yi[i]);
			roots[1+xi[i]] = cr;
		}
	}
}

int Crect(ll l, ll r, ll d, ll u) {
	l = lower_bound(xv, xv+xvn, l) - xv; r = lower_bound(xv, xv+xvn, r+1) - xv;
	d = lower_bound(yv, yv+yvn, d) - yv; u = lower_bound(yv, yv+yvn, u+1) - yv - 1;

	if (l>r || r<0 || d>u || u<0) return 0;

	int ret = pst.rsum(roots[r], d, u);
	if (l > 0) ret -= pst.rsum(roots[l], d, u);
	return ret;
}

ll Count(ll rad) {
	ll ret = 0;
	rep(i, n) ret += Crect(p[i].x-rad, p[i].x+rad, p[i].y-rad, p[i].y+rad);
	return ret;
}

ll ans[maxn], an;

void Add(int i, int j) {
	ans[an++] = max(abs(p[i].x-p[j].x), abs(p[i].y-p[j].y));
}

void Enumerate(ll rad) {
	rep(i, n) {
		ll l = p[i].x-rad, r = p[i].x+rad, d = p[i].y-rad, u = p[i].y+rad;
		l = lower_bound(xv, xv+xvn, l) - xv; r = lower_bound(xv, xv+xvn, r+1) - xv - 1;
		d = lower_bound(yv, yv+yvn, d) - yv; u = lower_bound(yv, yv+yvn, u) - yv - 1;
	}
}

int main()
{
	In(); Cc(); Bt();

	ll l = 0, r = ll(1e9) * 5;
	while (l+1 < r) {
		ll mid = (l+r)/2;
		ll tmp = Count(mid);
		tmp -= n; tmp /= 2;
		if (tmp >= k) r = mid;
		else l = mid;
	}

	Enumerate(l);
	sort(ans, ans+an);
	while (an < k) ans[an++] = r;

	rep(i, k) cout << ans[i] << '\n';

	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'void Cc()':
road_construction.cpp:5:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    5 | #define rep(i, n) for (int i=0; i<(n); ++i)
      |                   ^~~
road_construction.cpp:26:2: note: in expansion of macro 'rep'
   26 |  rep(i, n) xv[i] = p[i].x; sort(xv, xv+n); xvn = unique(xv, xv+n) - xv; rep(i, n) xi[i] = lower_bound(xv, xv+xvn, p[i].x) - xv;
      |  ^~~
road_construction.cpp:26:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   26 |  rep(i, n) xv[i] = p[i].x; sort(xv, xv+n); xvn = unique(xv, xv+n) - xv; rep(i, n) xi[i] = lower_bound(xv, xv+xvn, p[i].x) - xv;
      |                            ^~~~
road_construction.cpp:5:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    5 | #define rep(i, n) for (int i=0; i<(n); ++i)
      |                   ^~~
road_construction.cpp:27:2: note: in expansion of macro 'rep'
   27 |  rep(i, n) yv[i] = p[i].y; sort(yv, yv+n); yvn = unique(yv, yv+n) - yv; rep(i, n) yi[i] = lower_bound(yv, yv+yvn, p[i].y) - yv;
      |  ^~~
road_construction.cpp:27:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   27 |  rep(i, n) yv[i] = p[i].y; sort(yv, yv+n); yvn = unique(yv, yv+n) - yv; rep(i, n) yi[i] = lower_bound(yv, yv+yvn, p[i].y) - yv;
      |                            ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35