#include "jumps.h"
#include <vector>
int subtask = -1;
#define MAX_N 200000
#define MAX_M (2*MAX_N)
int tin[MAX_N], tout[MAX_N], head[MAX_N], nxt[MAX_M], vv[MAX_M], indeg[MAX_N], rt, timer, dd[MAX_N];
void link(int u, int v)
{
static int i = 1;
nxt[i] = head[u];
vv[i] = v;
++indeg[v];
head[u] = i++;
}
void dfs(int u)
{
tin[u] = timer++;
for (int j = head[u]; j; j = nxt[j]) dd[vv[j]] = dd[u] + 1, dfs(vv[j]);
tout[u] = timer - 1;
}
void init(int N, std::vector<int> H) {
if (N <= 200) subtask = 2;
else if (N <= 2000) subtask = 3;
int flag = 1;
for (int i = 1; i < N; ++i) if (H[i] != H[i-1] + 1) flag = 0;
if(flag) subtask = 1;
static int stk[MAX_N], so;
so = 0;
for (int i = 0; i < N; stk[so++] = i++)
while (so && H[stk[so-1]] < H[i]) link(stk[--so], i);
so = 0;
for (int i = N - 1; i >= 0; stk[so++] = i--)
while (so && H[stk[so-1]] < H[i]) link(stk[--so], i);
for (int i = 0; i < N; ++i)
if (indeg[i] == 0) rt = i;
dfs(rt);
}
int minimum_jumps(int A, int B, int C, int D) {
if (subtask == 1)
{
if (A > D) return -1;
if (B >= C) return 0;
return C - B;
}
int z = 1e9;
for (int i = A; i <= B; ++i)
for (int j = C; j <= D; ++j)
if (tin[i] <= tin[j] && tout[j] <= tout[i] && dd[j] - dd[i] < z) z = dd[j] - dd[i];
if (z == 1e9) return -1;
return z;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
63 ms |
15496 KB |
Output is correct |
4 |
Correct |
532 ms |
18196 KB |
Output is correct |
5 |
Correct |
530 ms |
11584 KB |
Output is correct |
6 |
Correct |
543 ms |
18256 KB |
Output is correct |
7 |
Correct |
426 ms |
14024 KB |
Output is correct |
8 |
Correct |
553 ms |
18360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4692 KB |
Output is correct |
4 |
Incorrect |
132 ms |
6428 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
1 ms |
4692 KB |
Output is correct |
4 |
Incorrect |
132 ms |
6428 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
63 ms |
15496 KB |
Output is correct |
4 |
Correct |
532 ms |
18196 KB |
Output is correct |
5 |
Correct |
530 ms |
11584 KB |
Output is correct |
6 |
Correct |
543 ms |
18256 KB |
Output is correct |
7 |
Correct |
426 ms |
14024 KB |
Output is correct |
8 |
Correct |
553 ms |
18360 KB |
Output is correct |
9 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |