#include <stdio.h>
#include <stdlib.h>
#define N 100000
#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 *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 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 + x;
d_ = INF;
if (rr_[i] >= j && ll_[j] <= i) {
d_ = d + x;
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, x + 1));
d_ = min(d_, solve(rr[i], j, d, x + 1));
d_ = min(d_, solve(i, ll[j], d, x + 1));
d_ = min(d_, solve(i, rr[j], d, x + 1));
}
return d_;
}
int main() {
static int qu[N];
int 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, 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, 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;
}
}
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:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d%d", &n, &k, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
railway_trip.c:115:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | 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 |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 KB |
Output is correct |
| 2 |
Correct |
23 ms |
8936 KB |
Output is correct |
| 3 |
Correct |
23 ms |
9000 KB |
Output is correct |
| 4 |
Correct |
22 ms |
8956 KB |
Output is correct |
| 5 |
Correct |
23 ms |
8944 KB |
Output is correct |
| 6 |
Correct |
24 ms |
9012 KB |
Output is correct |
| 7 |
Correct |
24 ms |
8964 KB |
Output is correct |
| 8 |
Incorrect |
21 ms |
7856 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
468 ms |
9596 KB |
Output is correct |
| 2 |
Correct |
526 ms |
9536 KB |
Output is correct |
| 3 |
Correct |
495 ms |
10044 KB |
Output is correct |
| 4 |
Correct |
511 ms |
10000 KB |
Output is correct |
| 5 |
Correct |
496 ms |
10060 KB |
Output is correct |
| 6 |
Correct |
553 ms |
9984 KB |
Output is correct |
| 7 |
Correct |
490 ms |
9944 KB |
Output is correct |
| 8 |
Correct |
308 ms |
10248 KB |
Output is correct |
| 9 |
Incorrect |
231 ms |
9008 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
461 ms |
9540 KB |
Output is correct |
| 2 |
Correct |
374 ms |
9624 KB |
Output is correct |
| 3 |
Correct |
538 ms |
9416 KB |
Output is correct |
| 4 |
Correct |
478 ms |
9844 KB |
Output is correct |
| 5 |
Incorrect |
230 ms |
9036 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
