Submission #683607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683607	2023-01-18T21:04:50 Z	rainboy	Railway Trip (JOI17_railway_trip)	C	100 / 100	494 ms	35236 KB

railway_trip

#include <stdio.h>

#define N	100000
#define H	18	/* H = ceil(log2(N * 2)) */
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int aa[N], ll[N], ll_[N], ddl[N], rr[N], rr_[N], ddr[N], n;

int solve(int i, int j, int d, int x) {
	int d_, tmp;

	if (i > j)
		tmp = i, i = j, j = tmp;
	if (i == -1 || j == n)
		return INF;
	if (i == j)
		return d;
	d_ = INF;
	if (rr_[i] >= j && ll_[j] <= i) {
		d_ = d;
		if (aa[i] < aa[j])
			d_ += ddr[i];
		else if (aa[i] > aa[j])
			d_ += ddl[j];
		else
			d_ += ddl[j] - ddl[i];
	}
	if (x < 4) {
		d_ = min(d_, solve(ll_[i], j, d + ddl[i], x + 1));
		d_ = min(d_, solve(rr_[i], j, d + ddr[i], x + 1));
		d_ = min(d_, solve(i, ll_[j], d + ddl[j], x + 1));
		d_ = min(d_, solve(i, rr_[j], d + ddr[j], x + 1));
	}
	return d_;
}

int goodl(int u, int j) {
	int i = u >> 1, s = u & 1;

	return s == 0 ? rr_[i] >= j : rr_[ll_[i]] >= j || rr_[rr_[i]] >= j;
}

int goodr(int v, int i) {
	int j = v >> 1, t = v & 1;

	return t == 0 ? ll_[j] <= i : ll_[ll_[j]] <= i || ll_[rr_[j]] <= i;
}

int main() {
	static int qu[N], pp[H + 1][N * 2], dd[H + 1][N * 2];
	int k, q, h, i, j, cnt;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		ll[i] = cnt == 0 ? -1 : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (i = 0; i < n; i++)
		if (ll[i] == -1)
			ll_[i] = -1, ddl[i] = 0;
		else if (aa[i] != aa[ll[i]])
			ll_[i] = ll[i], ddl[i] = 1;
		else
			ll_[i] = ll_[ll[i]], ddl[i] = ddl[ll[i]] + 1;
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		rr[i] = cnt == 0 ? n : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (i = n - 1; i >= 0; i--)
		if (rr[i] == n)
			rr_[i] = n, ddr[i] = 0;
		else if (aa[i] != aa[rr[i]])
			rr_[i] = rr[i], ddr[i] = 1;
		else
			rr_[i] = rr_[rr[i]], ddr[i] = ddr[rr[i]] + 1;
	for (i = 0; i < n; i++) {
		if (ll_[i] == -1 || rr_[i] == n)
			pp[0][i << 1 | 0] = i << 1 | 0, dd[0][i << 1 | 0] = 0;
		else if (ddl[i] < ddr[i])
			pp[0][i << 1 | 0] = ll_[i] << 1 | 0, dd[0][i << 1 | 0] = ddl[i];
		else if (ddl[i] > ddr[i])
			pp[0][i << 1 | 0] = rr_[i] << 1 | 0, dd[0][i << 1 | 0] = ddr[i];
		else
			pp[0][i << 1 | 0] = i << 1 | 1, dd[0][i << 1 | 0] = ddl[i];
		if (ll_[i] == -1 || rr_[i] == n || ll_[ll_[i]] == -1 || rr_[rr_[i]] == n)
			pp[0][i << 1 | 1] = i << 1 | 1, dd[0][i << 1 | 1] = 0;
		else if (aa[ll_[i]] > aa[rr_[i]])
			pp[0][i << 1 | 1] = ll_[i] << 1 | 0, dd[0][i << 1 | 1] = 0;
		else if (aa[ll_[i]] < aa[rr_[i]])
			pp[0][i << 1 | 1] = rr_[i] << 1 | 0, dd[0][i << 1 | 1] = 0;
		else if (ddl[ll_[i]] < ddr[rr_[i]])
			pp[0][i << 1 | 1] = ll_[ll_[i]] << 1 | 0, dd[0][i << 1 | 1] = ddl[ll_[i]];
		else if (ddl[ll_[i]] > ddr[rr_[i]])
			pp[0][i << 1 | 1] = rr_[rr_[i]] << 1 | 0, dd[0][i << 1 | 1] = ddr[rr_[i]];
		else
			pp[0][i << 1 | 1] = ll_[i] << 1 | 1, dd[0][i << 1 | 1] = ddl[ll_[i]];
	}
	for (h = 1; h <= H; h++)
		for (i = 0; i < n * 2; i++) {
			pp[h][i] = pp[h - 1][pp[h - 1][i]];
			dd[h][i] = dd[h - 1][i] + dd[h - 1][pp[h - 1][i]];
		}
	while (q--) {
		int s, t, u, v, d, d_;
		int tmp;

		scanf("%d%d", &i, &j), i--, j--;
		if (i > j)
			tmp = i, i = j, j = tmp;
		if (rr[i] >= j && ll[j] <= i) {
			d_ = 0;
			goto print;
		}
		d = 0;
		u = i << 1 | 0;
		for (h = H; h >= 0; h--)
			if (!goodl(pp[h][u], j))
				d += dd[h][u], u = pp[h][u];
		if (!goodl(u, j))
			d += dd[0][u], u = pp[0][u];
		v = j << 1 | 0;
		for (h = H; h >= 0; h--)
			if (!goodr(pp[h][v], i))
				d += dd[h][v], v = pp[h][v];
		if (!goodr(v, i))
			d += dd[0][v], v = pp[0][v];
		s = u & 1, u >>= 1, t = v & 1, v >>= 1;
		d_ = INF;
		if (s == 0 && t == 0)
			d_ = min(d_, solve(u, v, d, 0) - 1);
		else if (s == 0 && t == 1) {
			d_ = min(d_, solve(u, ll_[v], d, 0) - 1);
			d_ = min(d_, solve(u, rr_[v], d, 0) - 1);
		} else if (s == 1 && t == 0) {
			d_ = min(d_, solve(ll_[u], v, d, 0) - 1);
			d_ = min(d_, solve(rr_[u], v, d, 0) - 1);
		} else {
			d_ = min(d_, solve(ll_[u], ll_[v], d, 0) - 1);
			d_ = min(d_, solve(ll_[u], rr_[v], d, 0) - 1);
			d_ = min(d_, solve(rr_[u], ll_[v], d, 0) - 1);
			d_ = min(d_, solve(rr_[u], rr_[v], d, 0) - 1);
		}
print:
		printf("%d\n", d_);
	}
	return 0;
}

Compilation message

railway_trip.c: In function 'main':
railway_trip.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
railway_trip.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	0 ms	468 KB	Output is correct
5	Correct	0 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	0 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	852 KB	Output is correct
2	Correct	28 ms	32716 KB	Output is correct
3	Correct	31 ms	32724 KB	Output is correct
4	Correct	31 ms	32668 KB	Output is correct
5	Correct	31 ms	32756 KB	Output is correct
6	Correct	40 ms	32700 KB	Output is correct
7	Correct	33 ms	32628 KB	Output is correct
8	Correct	26 ms	33112 KB	Output is correct
9	Correct	30 ms	33028 KB	Output is correct
10	Correct	29 ms	32980 KB	Output is correct
11	Correct	31 ms	32868 KB	Output is correct
12	Correct	31 ms	32908 KB	Output is correct
13	Correct	31 ms	32856 KB	Output is correct
14	Correct	30 ms	32856 KB	Output is correct
15	Correct	31 ms	32788 KB	Output is correct
16	Correct	32 ms	32876 KB	Output is correct
17	Correct	33 ms	32728 KB	Output is correct
18	Correct	31 ms	32720 KB	Output is correct
19	Correct	31 ms	32728 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	33224 KB	Output is correct
2	Correct	151 ms	33380 KB	Output is correct
3	Correct	168 ms	33248 KB	Output is correct
4	Correct	169 ms	33120 KB	Output is correct
5	Correct	196 ms	33216 KB	Output is correct
6	Correct	158 ms	33136 KB	Output is correct
7	Correct	166 ms	33172 KB	Output is correct
8	Correct	187 ms	33504 KB	Output is correct
9	Correct	140 ms	33612 KB	Output is correct
10	Correct	232 ms	33740 KB	Output is correct
11	Correct	241 ms	33744 KB	Output is correct
12	Correct	244 ms	33796 KB	Output is correct
13	Correct	255 ms	33868 KB	Output is correct
14	Correct	166 ms	33480 KB	Output is correct
15	Correct	184 ms	33324 KB	Output is correct
16	Correct	197 ms	33216 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	280 ms	33036 KB	Output is correct
2	Correct	346 ms	32988 KB	Output is correct
3	Correct	212 ms	33036 KB	Output is correct
4	Correct	235 ms	33012 KB	Output is correct
5	Correct	142 ms	33624 KB	Output is correct
6	Correct	357 ms	33724 KB	Output is correct
7	Correct	318 ms	35236 KB	Output is correct
8	Correct	283 ms	35160 KB	Output is correct
9	Correct	365 ms	35124 KB	Output is correct
10	Correct	340 ms	35064 KB	Output is correct
11	Correct	400 ms	35048 KB	Output is correct
12	Correct	352 ms	35076 KB	Output is correct
13	Correct	358 ms	35100 KB	Output is correct
14	Correct	473 ms	35212 KB	Output is correct
15	Correct	486 ms	35152 KB	Output is correct
16	Correct	494 ms	35176 KB	Output is correct
17	Correct	299 ms	35100 KB	Output is correct
18	Correct	317 ms	35048 KB	Output is correct
19	Correct	312 ms	35220 KB	Output is correct
20	Correct	177 ms	34796 KB	Output is correct
21	Correct	492 ms	34804 KB	Output is correct
22	Correct	454 ms	34756 KB	Output is correct
23	Correct	406 ms	34792 KB	Output is correct