#include <bits/stdc++.h>
struct Seg {
int size;
std::vector <int> min;
std::vector <int> max;
Seg(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
max.resize(size << 1, -1);
min.resize(size << 1, 1 << 30);
}
inline void build(const std::vector <int>& mn, const std::vector <int>& mx) {
build(mn, mx, 0, 0, size);
}
void build(const std::vector <int>& mn, const std::vector <int>& mx, int now, int l, int r) {
if (!(r - l - 1)) {
if (l < (int) mn.size()) {
min[now] = mn[l];
}
if (l < (int) mx.size()) {
max[now] = mx[l];
}
return;
}
int mid = (l + r) >> 1;
build(mn, mx, now * 2 + 1, l, mid);
build(mn, mx, now * 2 + 2, mid, r);
max[now] = std::max(max[now * 2 + 1], max[now * 2 + 2]);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
}
inline int query_min(int l, int r) {
return query_min(l, r, 0, 0, size);
}
int query_min(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return 1 << 30;
}
if (l >= tl && r <= tr) {
return min[now];
}
int mid = (l + r) >> 1;
return std::min(query_min(tl, tr, now * 2 + 1, l, mid), query_min(tl, tr, now * 2 + 2, mid, r));
}
inline int query_max(int l, int r) {
return query_max(l, r, 0, 0, size);
}
int query_max(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return -1;
}
if (l >= tl && r <= tr) {
return max[now];
}
int mid = (l + r) >> 1;
return std::max(query_max(tl, tr, now * 2 + 1, l, mid), query_max(tl, tr, now * 2 + 2, mid, r));
}
};
struct Cycle {
std::vector <int> c;
int l, r;
};
long long minimum_walk(std::vector <int> p, int s) {
int n = p.size();
while (s < (int) p.size() - 1 && p[n - 1] == n - 1) {
p.pop_back();
n--;
}
int begrem = 0;
while (begrem < s && p[begrem] == begrem) {
begrem++;
}
p.erase(p.begin(), p.begin() + begrem);
n = p.size();
if (!n) {
return 0;
}
std::vector <bool> vis(n, false);
std::vector <Cycle> cyc;
std::vector <int> part(n, -1);
long long ans = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
vis[i] = true;
int part_now = cyc.size();
cyc.resize(cyc.size() + 1);
cyc.back().c = { i };
cyc.back().l = cyc.back().r = i;
ans += abs(i - p[i]);
int v = p[i];
part[i] = part_now;
while (v != i) {
vis[v] = true;
cyc.back().c.push_back(v);
cyc.back().l = std::min(cyc.back().l, v);
cyc.back().r = std::max(cyc.back().r, v);
part[v] = part_now;
ans += abs(v - p[v]);
v = p[v];
};
}
Seg seg(n);
std::vector <int> mn(n), mx(n);
for (int i = 0; i < n; i++) {
mn[i] = cyc[part[i]].l;
mx[i] = cyc[part[i]].r;
}
seg.build(mn, mx);
int cmps = 0;
int l = 0, r = 0;
int last;
int ll = -1, rr = -1;
while (r < n) {
while ((last = seg.query_max(l, r + 1)) > r) {
r = last;
}
if (l <= s && r >= s) {
ll = l;
rr = r;
}
l = ++r;
cmps++;
}
l = s, r = s;
int last_l, last_r;
cmps--;
while (l >= ll) {
while (true) {
last_l = seg.query_min(l, r + 1);
last_r = seg.query_max(l, r + 1);
if (last_l >= l && last_r <= r) {
break;
}
l = last_l;
r = last_r;
}
l--;
r++;
cmps++;
}
return ans + (cmps - 1) * 2;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:127:15: warning: variable 'rr' set but not used [-Wunused-but-set-variable]
127 | int ll = -1, rr = -1;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
4 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
4 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
280 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
4 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
280 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
177 ms |
41372 KB |
Output is correct |
31 |
Correct |
196 ms |
41632 KB |
Output is correct |
32 |
Correct |
80 ms |
8044 KB |
Output is correct |
33 |
Correct |
280 ms |
79820 KB |
Output is correct |
34 |
Correct |
269 ms |
79932 KB |
Output is correct |
35 |
Correct |
251 ms |
71380 KB |
Output is correct |
36 |
Correct |
191 ms |
55012 KB |
Output is correct |
37 |
Correct |
128 ms |
43652 KB |
Output is correct |
38 |
Correct |
125 ms |
42344 KB |
Output is correct |
39 |
Correct |
125 ms |
42092 KB |
Output is correct |
40 |
Correct |
126 ms |
41072 KB |
Output is correct |
41 |
Correct |
136 ms |
40844 KB |
Output is correct |
42 |
Correct |
142 ms |
40808 KB |
Output is correct |
43 |
Correct |
193 ms |
82832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
360 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 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
4 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
280 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
177 ms |
41372 KB |
Output is correct |
31 |
Correct |
196 ms |
41632 KB |
Output is correct |
32 |
Correct |
80 ms |
8044 KB |
Output is correct |
33 |
Correct |
280 ms |
79820 KB |
Output is correct |
34 |
Correct |
269 ms |
79932 KB |
Output is correct |
35 |
Correct |
251 ms |
71380 KB |
Output is correct |
36 |
Correct |
191 ms |
55012 KB |
Output is correct |
37 |
Correct |
128 ms |
43652 KB |
Output is correct |
38 |
Correct |
125 ms |
42344 KB |
Output is correct |
39 |
Correct |
125 ms |
42092 KB |
Output is correct |
40 |
Correct |
126 ms |
41072 KB |
Output is correct |
41 |
Correct |
136 ms |
40844 KB |
Output is correct |
42 |
Correct |
142 ms |
40808 KB |
Output is correct |
43 |
Correct |
193 ms |
82832 KB |
Output is correct |
44 |
Correct |
1 ms |
360 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
1 ms |
340 KB |
Output is correct |
50 |
Correct |
1 ms |
340 KB |
Output is correct |
51 |
Correct |
1 ms |
340 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
54 |
Halted |
0 ms |
0 KB |
- |