Submission #666202

#	Time	Username	Problem	Language	Result	Execution time	Memory
666202		rainboy	Road Construction (JOI21_road_construction)	C11	100 / 100	4447 ms	19112 KiB

road_construction

#include <stdio.h>

#define N	250000
#define M	250000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long abs_(long long a) { return a > 0 ? a : -a; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

long long xx[N], yy[N]; int ii[N], n;
long long dd[M]; int hh[M], m;

long long *vv;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (vv[ii[j]] == vv[i_])
				j++;
			else if (vv[ii[j]] < vv[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int zz[N + 1], ll[N + 1], rr[N + 1], ii_[N + 1], _, u_, l_, r_;

int node(int i) {
	zz[_] = rand_();
	ll[_] = rr[_] = 0;
	ii_[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = yy[ii_[u]] != yy[i] ? (yy[ii_[u]] < yy[i] ? -1 : 1) : ii_[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i);
	u_ = merge(l_, r_);
}

int tr_higher(long long y, int i) {
	int u = u_, i_ = -1;

	while (u)
		if (yy[ii_[u]] < y || yy[ii_[u]] == y && ii_[u] <= i)
			u = rr[u];
		else
			i_ = ii_[u], u = ll[u];
	return i_;
}

int count(int m, long long d) {
	int i, i_, j, j_, cnt;

	cnt = 0, _ = 1, u_ = 0;
	for (i = 0, j = 0; j < n; j++) {
		j_ = ii[j];
		while (xx[j_] - xx[i_ = ii[i]] > d)
			tr_remove(i_), i++;
		i_ = tr_higher(yy[j_] - d, -1);
		while (i_ != -1 && yy[i_] - yy[j_] <= d) {
			dd[cnt++] = max(abs_(xx[i_] - xx[j_]), abs_(yy[i_] - yy[j_]));
			if (cnt == m)
				return m;
			i_ = tr_higher(yy[i_], i_);
		}
		tr_add(j_);
	}
	return cnt;
}

int main() {
	int cnt, h, i;
	long long lower, upper, d;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		int x, y;

		scanf("%d%d", &x, &y);
		xx[i] = x + y, yy[i] = x - y;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	vv = xx, sort(ii, 0, n);
	lower = 0, upper = INF;
	while (upper - lower > 1) {
		d = (lower + upper) / 2;
		if (count(m, d) < m)
			lower = d;
		else
			upper = d;
	}
	d = upper;
	cnt = count(m, d - 1);
	while (cnt < m)
		dd[cnt++] = d;
	for (h = 0; h < m; h++)
		hh[h] = h;
	vv = dd, sort(hh, 0, m);
	for (h = 0; h < m; h++)
		printf("%lld\n", dd[hh[h]]);
	return 0;
}

Compilation message (stderr)

road_construction.c: In function 'tr_higher':
road_construction.c:97:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |   if (yy[ii_[u]] < y || yy[ii_[u]] == y && ii_[u] <= i)
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
road_construction.c: In function 'main':
road_construction.c:128:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
road_construction.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~

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