oj.uz

Submission #666202

# Submission time Handle Problem Language Result Execution time Memory
666202 2022-11-27T17:38:02 Z rainboy Road Construction (JOI21_road_construction) C
100 / 100
 4447 ms 19112 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 5992 KB Output is correct
2 Correct 877 ms 5792 KB Output is correct
3 Correct 827 ms 5892 KB Output is correct
4 Correct 802 ms 5880 KB Output is correct
5 Correct 814 ms 4764 KB Output is correct
6 Correct 11 ms 412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 16244 KB Output is correct
2 Correct 905 ms 16208 KB Output is correct
3 Correct 823 ms 5764 KB Output is correct
4 Correct 1022 ms 15988 KB Output is correct
5 Correct 852 ms 16184 KB Output is correct
6 Correct 845 ms 16236 KB Output is correct
7 Correct 865 ms 15640 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 14168 KB Output is correct
2 Correct 335 ms 14140 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 164 ms 11992 KB Output is correct
5 Correct 1211 ms 14480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 14168 KB Output is correct
2 Correct 335 ms 14140 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 164 ms 11992 KB Output is correct
5 Correct 1211 ms 14480 KB Output is correct
6 Correct 498 ms 14288 KB Output is correct
7 Correct 455 ms 14264 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 373 ms 14264 KB Output is correct
11 Correct 145 ms 12116 KB Output is correct
12 Correct 1220 ms 14520 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 5992 KB Output is correct
2 Correct 877 ms 5792 KB Output is correct
3 Correct 827 ms 5892 KB Output is correct
4 Correct 802 ms 5880 KB Output is correct
5 Correct 814 ms 4764 KB Output is correct
6 Correct 11 ms 412 KB Output is correct
7 Correct 2508 ms 10716 KB Output is correct
8 Correct 2625 ms 10776 KB Output is correct
9 Correct 812 ms 5896 KB Output is correct
10 Correct 1346 ms 9984 KB Output is correct
11 Correct 1123 ms 9900 KB Output is correct
12 Correct 1904 ms 10740 KB Output is correct
13 Correct 1881 ms 9332 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 5992 KB Output is correct
2 Correct 877 ms 5792 KB Output is correct
3 Correct 827 ms 5892 KB Output is correct
4 Correct 802 ms 5880 KB Output is correct
5 Correct 814 ms 4764 KB Output is correct
6 Correct 11 ms 412 KB Output is correct
7 Correct 963 ms 16244 KB Output is correct
8 Correct 905 ms 16208 KB Output is correct
9 Correct 823 ms 5764 KB Output is correct
10 Correct 1022 ms 15988 KB Output is correct
11 Correct 852 ms 16184 KB Output is correct
12 Correct 845 ms 16236 KB Output is correct
13 Correct 865 ms 15640 KB Output is correct
14 Correct 245 ms 14168 KB Output is correct
15 Correct 335 ms 14140 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 164 ms 11992 KB Output is correct
18 Correct 1211 ms 14480 KB Output is correct
19 Correct 498 ms 14288 KB Output is correct
20 Correct 455 ms 14264 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 352 KB Output is correct
23 Correct 373 ms 14264 KB Output is correct
24 Correct 145 ms 12116 KB Output is correct
25 Correct 1220 ms 14520 KB Output is correct
26 Correct 2508 ms 10716 KB Output is correct
27 Correct 2625 ms 10776 KB Output is correct
28 Correct 812 ms 5896 KB Output is correct
29 Correct 1346 ms 9984 KB Output is correct
30 Correct 1123 ms 9900 KB Output is correct
31 Correct 1904 ms 10740 KB Output is correct
32 Correct 1881 ms 9332 KB Output is correct
33 Correct 4420 ms 19016 KB Output is correct
34 Correct 4447 ms 19064 KB Output is correct
35 Correct 2494 ms 18240 KB Output is correct
36 Correct 2701 ms 19112 KB Output is correct
37 Correct 3042 ms 19064 KB Output is correct
38 Correct 3046 ms 17776 KB Output is correct