#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;
}
Compilation message
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--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
292 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
4872 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
4856 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
5004 KB |
Output is correct |
| 2 |
Correct |
63 ms |
4964 KB |
Output is correct |
| 3 |
Incorrect |
65 ms |
4860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
