#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 (i = 0; i < n * 2; i++)
printf("%d(%d) ", pp[0][i], dd[0][i]);
printf("\n");
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:120:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
35044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
307 ms |
34908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
