Submission #683607

#	Time	Username	Problem	Language	Result	Execution time	Memory
683607		rainboy	Railway Trip (JOI17_railway_trip)	C11	100 / 100	494 ms	35236 KiB

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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55