#include <stdio.h>
#include <stdlib.h>
#define N 100000
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int bfs(int n, int s, int t) {
static int qu[N], dd[N];
int cnt, h, i, j, d, o;
for (i = 0; i < n; i++)
dd[i] = n;
cnt = 0;
dd[s] = 0, qu[cnt++] = s;
for (h = 0; h < cnt; h++) {
i = qu[h], d = dd[i] + 1;
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (dd[j] > d)
dd[j] = d, qu[cnt++] = j;
}
}
return dd[t];
}
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;
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0; i < n; i++)
if (ll[i] != -1)
append(i, ll[i]), append(ll[i], i);
for (i = 0; i < n; i++)
if (rr[i] != n)
append(i, rr[i]), append(rr[i], i);
while (q--) {
int s, t, u, v, d;
int tmp;
scanf("%d%d", &i, &j), i--, j--;
printf("%d\n", bfs(n, i, j) - 1);
continue;
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;
}
Compilation message
railway_trip.c: In function 'main':
railway_trip.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d%d%d", &n, &k, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
railway_trip.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
296 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
168 ms |
9932 KB |
Output is correct |
| 3 |
Correct |
166 ms |
9800 KB |
Output is correct |
| 4 |
Correct |
158 ms |
9816 KB |
Output is correct |
| 5 |
Correct |
165 ms |
9864 KB |
Output is correct |
| 6 |
Correct |
177 ms |
9844 KB |
Output is correct |
| 7 |
Correct |
159 ms |
10068 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8692 KB |
Output is correct |
| 9 |
Correct |
64 ms |
10444 KB |
Output is correct |
| 10 |
Correct |
67 ms |
9660 KB |
Output is correct |
| 11 |
Correct |
148 ms |
10252 KB |
Output is correct |
| 12 |
Correct |
137 ms |
10172 KB |
Output is correct |
| 13 |
Correct |
135 ms |
10204 KB |
Output is correct |
| 14 |
Correct |
146 ms |
10184 KB |
Output is correct |
| 15 |
Correct |
148 ms |
10244 KB |
Output is correct |
| 16 |
Correct |
135 ms |
10204 KB |
Output is correct |
| 17 |
Correct |
169 ms |
10164 KB |
Output is correct |
| 18 |
Correct |
201 ms |
10188 KB |
Output is correct |
| 19 |
Correct |
76 ms |
9308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2081 ms |
9548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
9548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
