#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
const int INF = 2e6;
vector<vector<int>> adj(2000);
vector<vector<int>> dist(2000, vector<int>(2000, INF));
int powtwo = (int)pow(2, __lg(2000) + !!(2000 & (2000-1)));
void bfs(int x)
{
queue<int> q;
vector<bool> visited(n);
int start = x;
visited[start] = true;
dist[start][start] = 0;
q.push(start);
while (!q.empty()) {
int s = q.front(); q.pop();
for (auto u : adj[s]) {
if (visited[u]) continue;
visited[u] = true;
dist[start][u] = dist[start][s]+1;
q.push(u);
}
}
}
struct SegmentTree {
vector<int> t;
SegmentTree(int power) : t(2*power) {}
void build(vector<int>& a, int v, int tl, int tr) {
if (tl == tr) {
if (tl < (int)a.size()) t[v] = a[tl];
else t[v] = INF;
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = min(t[v*2], t[v*2+1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return INF;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return min(query(v*2, tl, tm, l, min(r, tm)),
query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
};
vector<SegmentTree> segdist;
void init(int N, std::vector<int> H) {
n = N;
for (auto u: H) {h.push_back(u);}
h.shrink_to_fit();
for (int i=0; i<n; i++)
{
for (int j=i; j<n; j++)
{
if (h[i] < h[j]) {adj[i].push_back(j); break;};
}
for (int j=i; j>=0; j--)
{
if (h[i] < h[j]) {adj[i].push_back(j); break;};
}
}
for (int i=0; i<n; i++) {bfs(i);}
for (int i=0; i<n; i++)
{
SegmentTree segtree(powtwo);
segtree.build(dist[i], 1, 0, powtwo-1);
segdist.push_back(segtree);
}
}
int minimum_jumps(int A, int B, int C, int D) {
int answer = INF;
for (int i=A; i<=B; i++)
{
answer = min(answer, segdist[i].query(1, 0, powtwo-1, C, D));
}
return (answer >= INF ? -1 : answer);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16216 KB |
Output is correct |
2 |
Correct |
9 ms |
16092 KB |
Output is correct |
3 |
Runtime error |
37 ms |
36444 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16348 KB |
Output is correct |
2 |
Correct |
8 ms |
16216 KB |
Output is correct |
3 |
Correct |
8 ms |
16216 KB |
Output is correct |
4 |
Correct |
8 ms |
16216 KB |
Output is correct |
5 |
Correct |
12 ms |
16508 KB |
Output is correct |
6 |
Correct |
18 ms |
19464 KB |
Output is correct |
7 |
Correct |
12 ms |
19076 KB |
Output is correct |
8 |
Correct |
13 ms |
19464 KB |
Output is correct |
9 |
Correct |
11 ms |
18804 KB |
Output is correct |
10 |
Correct |
13 ms |
19468 KB |
Output is correct |
11 |
Correct |
18 ms |
19444 KB |
Output is correct |
12 |
Correct |
16 ms |
19464 KB |
Output is correct |
13 |
Correct |
14 ms |
19544 KB |
Output is correct |
14 |
Correct |
19 ms |
19288 KB |
Output is correct |
15 |
Correct |
14 ms |
19604 KB |
Output is correct |
16 |
Correct |
12 ms |
19460 KB |
Output is correct |
17 |
Correct |
14 ms |
19460 KB |
Output is correct |
18 |
Correct |
9 ms |
16268 KB |
Output is correct |
19 |
Correct |
10 ms |
16860 KB |
Output is correct |
20 |
Correct |
14 ms |
19544 KB |
Output is correct |
21 |
Correct |
14 ms |
19468 KB |
Output is correct |
22 |
Correct |
17 ms |
19544 KB |
Output is correct |
23 |
Correct |
14 ms |
19676 KB |
Output is correct |
24 |
Correct |
12 ms |
19464 KB |
Output is correct |
25 |
Correct |
8 ms |
16316 KB |
Output is correct |
26 |
Correct |
8 ms |
16216 KB |
Output is correct |
27 |
Correct |
8 ms |
16216 KB |
Output is correct |
28 |
Correct |
12 ms |
19468 KB |
Output is correct |
29 |
Correct |
11 ms |
19468 KB |
Output is correct |
30 |
Correct |
12 ms |
19488 KB |
Output is correct |
31 |
Correct |
12 ms |
19460 KB |
Output is correct |
32 |
Correct |
13 ms |
19468 KB |
Output is correct |
33 |
Correct |
9 ms |
16272 KB |
Output is correct |
34 |
Correct |
11 ms |
19064 KB |
Output is correct |
35 |
Correct |
11 ms |
19464 KB |
Output is correct |
36 |
Correct |
12 ms |
19460 KB |
Output is correct |
37 |
Correct |
13 ms |
19460 KB |
Output is correct |
38 |
Correct |
11 ms |
19464 KB |
Output is correct |
39 |
Correct |
12 ms |
19468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16348 KB |
Output is correct |
2 |
Correct |
8 ms |
16216 KB |
Output is correct |
3 |
Correct |
8 ms |
16216 KB |
Output is correct |
4 |
Correct |
8 ms |
16216 KB |
Output is correct |
5 |
Correct |
12 ms |
16508 KB |
Output is correct |
6 |
Correct |
18 ms |
19464 KB |
Output is correct |
7 |
Correct |
12 ms |
19076 KB |
Output is correct |
8 |
Correct |
13 ms |
19464 KB |
Output is correct |
9 |
Correct |
11 ms |
18804 KB |
Output is correct |
10 |
Correct |
13 ms |
19468 KB |
Output is correct |
11 |
Correct |
18 ms |
19444 KB |
Output is correct |
12 |
Correct |
16 ms |
19464 KB |
Output is correct |
13 |
Correct |
14 ms |
19544 KB |
Output is correct |
14 |
Correct |
19 ms |
19288 KB |
Output is correct |
15 |
Correct |
14 ms |
19604 KB |
Output is correct |
16 |
Correct |
12 ms |
19460 KB |
Output is correct |
17 |
Correct |
14 ms |
19460 KB |
Output is correct |
18 |
Correct |
9 ms |
16268 KB |
Output is correct |
19 |
Correct |
10 ms |
16860 KB |
Output is correct |
20 |
Correct |
14 ms |
19544 KB |
Output is correct |
21 |
Correct |
14 ms |
19468 KB |
Output is correct |
22 |
Correct |
17 ms |
19544 KB |
Output is correct |
23 |
Correct |
14 ms |
19676 KB |
Output is correct |
24 |
Correct |
12 ms |
19464 KB |
Output is correct |
25 |
Correct |
8 ms |
16316 KB |
Output is correct |
26 |
Correct |
8 ms |
16216 KB |
Output is correct |
27 |
Correct |
8 ms |
16216 KB |
Output is correct |
28 |
Correct |
12 ms |
19468 KB |
Output is correct |
29 |
Correct |
11 ms |
19468 KB |
Output is correct |
30 |
Correct |
12 ms |
19488 KB |
Output is correct |
31 |
Correct |
12 ms |
19460 KB |
Output is correct |
32 |
Correct |
13 ms |
19468 KB |
Output is correct |
33 |
Correct |
9 ms |
16272 KB |
Output is correct |
34 |
Correct |
11 ms |
19064 KB |
Output is correct |
35 |
Correct |
11 ms |
19464 KB |
Output is correct |
36 |
Correct |
12 ms |
19460 KB |
Output is correct |
37 |
Correct |
13 ms |
19460 KB |
Output is correct |
38 |
Correct |
11 ms |
19464 KB |
Output is correct |
39 |
Correct |
12 ms |
19468 KB |
Output is correct |
40 |
Correct |
8 ms |
16216 KB |
Output is correct |
41 |
Correct |
9 ms |
16272 KB |
Output is correct |
42 |
Correct |
9 ms |
16268 KB |
Output is correct |
43 |
Correct |
10 ms |
16268 KB |
Output is correct |
44 |
Correct |
9 ms |
16512 KB |
Output is correct |
45 |
Correct |
13 ms |
19544 KB |
Output is correct |
46 |
Correct |
15 ms |
19032 KB |
Output is correct |
47 |
Correct |
13 ms |
19464 KB |
Output is correct |
48 |
Correct |
12 ms |
18800 KB |
Output is correct |
49 |
Correct |
13 ms |
19544 KB |
Output is correct |
50 |
Correct |
13 ms |
19464 KB |
Output is correct |
51 |
Correct |
13 ms |
19544 KB |
Output is correct |
52 |
Correct |
13 ms |
19464 KB |
Output is correct |
53 |
Correct |
13 ms |
19456 KB |
Output is correct |
54 |
Correct |
15 ms |
19552 KB |
Output is correct |
55 |
Correct |
12 ms |
19460 KB |
Output is correct |
56 |
Correct |
13 ms |
19544 KB |
Output is correct |
57 |
Correct |
11 ms |
19480 KB |
Output is correct |
58 |
Correct |
121 ms |
43700 KB |
Output is correct |
59 |
Correct |
184 ms |
48464 KB |
Output is correct |
60 |
Correct |
34 ms |
29604 KB |
Output is correct |
61 |
Correct |
196 ms |
48468 KB |
Output is correct |
62 |
Correct |
21 ms |
19552 KB |
Output is correct |
63 |
Correct |
224 ms |
48472 KB |
Output is correct |
64 |
Correct |
268 ms |
48472 KB |
Output is correct |
65 |
Correct |
242 ms |
48472 KB |
Output is correct |
66 |
Correct |
226 ms |
48716 KB |
Output is correct |
67 |
Correct |
190 ms |
48464 KB |
Output is correct |
68 |
Correct |
196 ms |
48692 KB |
Output is correct |
69 |
Correct |
170 ms |
48472 KB |
Output is correct |
70 |
Correct |
85 ms |
48472 KB |
Output is correct |
71 |
Correct |
8 ms |
16216 KB |
Output is correct |
72 |
Correct |
9 ms |
16868 KB |
Output is correct |
73 |
Correct |
12 ms |
19464 KB |
Output is correct |
74 |
Correct |
12 ms |
19460 KB |
Output is correct |
75 |
Correct |
13 ms |
19464 KB |
Output is correct |
76 |
Correct |
13 ms |
19460 KB |
Output is correct |
77 |
Correct |
15 ms |
19544 KB |
Output is correct |
78 |
Correct |
8 ms |
16216 KB |
Output is correct |
79 |
Correct |
8 ms |
16244 KB |
Output is correct |
80 |
Correct |
9 ms |
16312 KB |
Output is correct |
81 |
Correct |
12 ms |
19464 KB |
Output is correct |
82 |
Correct |
12 ms |
19464 KB |
Output is correct |
83 |
Correct |
13 ms |
19596 KB |
Output is correct |
84 |
Correct |
12 ms |
19464 KB |
Output is correct |
85 |
Correct |
14 ms |
19796 KB |
Output is correct |
86 |
Correct |
9 ms |
16268 KB |
Output is correct |
87 |
Correct |
11 ms |
19060 KB |
Output is correct |
88 |
Correct |
11 ms |
19464 KB |
Output is correct |
89 |
Correct |
11 ms |
19464 KB |
Output is correct |
90 |
Correct |
12 ms |
19464 KB |
Output is correct |
91 |
Correct |
11 ms |
19464 KB |
Output is correct |
92 |
Correct |
11 ms |
19468 KB |
Output is correct |
93 |
Correct |
11 ms |
19484 KB |
Output is correct |
94 |
Correct |
15 ms |
20312 KB |
Output is correct |
95 |
Correct |
148 ms |
48468 KB |
Output is correct |
96 |
Correct |
147 ms |
48604 KB |
Output is correct |
97 |
Correct |
131 ms |
48472 KB |
Output is correct |
98 |
Correct |
143 ms |
48472 KB |
Output is correct |
99 |
Correct |
122 ms |
48472 KB |
Output is correct |
100 |
Correct |
11 ms |
19480 KB |
Output is correct |
101 |
Correct |
21 ms |
28264 KB |
Output is correct |
102 |
Correct |
49 ms |
48720 KB |
Output is correct |
103 |
Correct |
68 ms |
48552 KB |
Output is correct |
104 |
Correct |
50 ms |
48472 KB |
Output is correct |
105 |
Correct |
64 ms |
48472 KB |
Output is correct |
106 |
Correct |
67 ms |
48468 KB |
Output is correct |
107 |
Correct |
11 ms |
19480 KB |
Output is correct |
108 |
Correct |
30 ms |
31224 KB |
Output is correct |
109 |
Correct |
53 ms |
48720 KB |
Output is correct |
110 |
Correct |
60 ms |
48684 KB |
Output is correct |
111 |
Correct |
42 ms |
48560 KB |
Output is correct |
112 |
Correct |
53 ms |
48496 KB |
Output is correct |
113 |
Correct |
71 ms |
48472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16348 KB |
Output is correct |
2 |
Correct |
8 ms |
16216 KB |
Output is correct |
3 |
Correct |
8 ms |
16168 KB |
Output is correct |
4 |
Correct |
8 ms |
16216 KB |
Output is correct |
5 |
Runtime error |
40 ms |
36568 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16224 KB |
Output is correct |
2 |
Correct |
8 ms |
16264 KB |
Output is correct |
3 |
Correct |
11 ms |
16208 KB |
Output is correct |
4 |
Runtime error |
31 ms |
34768 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16224 KB |
Output is correct |
2 |
Correct |
8 ms |
16264 KB |
Output is correct |
3 |
Correct |
11 ms |
16208 KB |
Output is correct |
4 |
Runtime error |
31 ms |
34768 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16216 KB |
Output is correct |
2 |
Correct |
9 ms |
16092 KB |
Output is correct |
3 |
Runtime error |
37 ms |
36444 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |