제출 #683591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683591		rainboy	Railway Trip (JOI17_railway_trip)	C11	0 / 100	67 ms	5004 KiB

railway_trip

#include <stdio.h>

#define N	100000

int main() {
	static int aa[N], qu[N], ll[N], ll_[N], ddl[N], rr[N], rr_[N], ddr[N];
	int n, k, q, 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;
	while (q--) {
		int s, t, u, v, 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) {
			printf("0\n");
			continue;
		}
		d = 0;
		u = i, s = 0;
		while ((s == 0 ? rr_[u] <= j : (rr_[ll_[u]] <= j && rr_[rr_[u]] <= j)))
			if (s == 0) {
				if (ddl[u] < ddr[u])
					d += ddl[u], u = ll_[u], s = 0;
				else if (ddl[u] > ddr[u])
					d += ddr[u], u = rr_[u], s = 0;
				else
					d += ddl[u], s = 1;
			} else {
				if (aa[ll_[u]] > aa[rr_[u]])
					u = ll_[u], s = 0;
				else if (aa[ll_[u]] < aa[rr_[u]])
					u = rr_[u], s = 0;
				else {
					if (ddl[ll_[u]] < ddr[rr_[u]])
						d += ddl[ll_[u]], u = ll_[ll_[u]], s = 0;
					else if (ddl[ll_[u]] > ddr[rr_[u]])
						d += ddr[rr_[u]], u = rr_[rr_[u]], s = 0;
					else
						d += ddl[ll_[u]], u = ll_[u], s = 1;
				}
			}
		v = j, t = 0;
		while ((t == 0 ? ll_[v] >= i : (ll_[ll_[v]] >= i && ll_[rr_[v]] >= i)))
			if (t == 0) {
				if (ddl[v] < ddr[v])
					d += ddl[v], v = ll_[v], t = 0;
				else if (ddl[v] > ddr[v])
					d += ddr[v], v = rr_[v], t = 0;
				else
					d += ddl[v], t = 1;
			} else {
				if (aa[ll_[v]] > aa[rr_[v]])
					v = ll_[v], t = 0;
				else if (aa[ll_[v]] < aa[rr_[v]])
					v = rr_[v], t = 0;
				else {
					if (ddl[ll_[v]] < ddr[rr_[v]])
						d += ddl[ll_[v]], v = ll_[ll_[v]], t = 0;
					else if (ddl[ll_[v]] > ddr[rr_[v]])
						d += ddr[rr_[v]], v = rr_[rr_[v]], t = 0;
					else
						d += ddl[ll_[v]], v = ll_[v], t = 1;
				}
			}
		if (s == 0 && t == 0) {
			if (u == v) {
				d--;
				goto print;
			}
		} else if (s == 0 && t == 1) {
			if (u == ll_[v] || u == rr_[v]) {
				d--;
				goto print;
			}
		} else if (s == 1 && t == 0) {
			if (v == ll_[u] || v == rr_[u]) {
				d--;
				goto print;
			}
		} else {
			if (ll_[u] == ll_[v] || ll_[u] == rr_[v] || rr_[u] == ll_[v] || rr_[u] == rr_[v]) {
				d--;
				goto print;
			}
		}
		if ((s == 0 ? rr[u] <= j : (rr[ll_[u]] <= j && rr[rr_[u]] <= j)) || (t == 0 ? ll[v] >= i : (ll[ll_[v]] >= i && ll[rr_[v]] >= i))) {
			if (s == 1)
				u = rr_[rr_[u]] > j ? rr_[u] : ll_[u];
			if (t == 1)
				v = ll_[ll_[v]] < i ? ll_[v] : rr_[v];
			if (aa[u] < aa[v])
				d += ddr[u];
			else if (aa[u] > aa[v])
				d += ddl[v];
			else
				d += ddl[v] - ddl[u];
			d--;
		}
print:
		printf("%d\n", d);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55