// #include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
const int N = 1e6 + 20, INF = 1e9;
int t[4 * N];
void modify(int v, int tl, int tr, int pos, int val){
if (tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) modify(2 * v + 1, tl, tm, pos, val);
else modify(2 * v + 2, tm + 1, tr, pos, val);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
int query(int v, int tl, int tr, int l, int r){
if (l > r) return INF;
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
return min(
query(2 * v + 1, tl, tm, l, min(r, tm)),
query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r)
);
}
long long minimum_walk(std::vector<int> p, int s) {
int n = sz(p);
ll ans = 0;
for (int i = 0; i < n; i++){
ans += abs(i - p[i]);
}
int mincycle = -1, maxcycle = -1;
for (int i = 0; i < n; i++) if (i != p[i]){
mincycle = i;
break;
}
for (int i = n - 1; i >= 0; i--) if (i != p[i]){
maxcycle = i;
break;
}
if (mincycle == -1) return 0;
for (int i = mincycle, mx = -1; i < n;){
mx = max(mx, p[i]);
if (mx <= i){
int j = i + 1;
while (j < n && j == p[j]) j++;
if (j == n) break;
ans += 2 * (j - i), i = j;
}
else i++;
}
if (s < mincycle) return ans + 2 * (mincycle - s);
if (s > maxcycle) return ans + 2 * (s - maxcycle);
vector<bool> cycleend(n);
for (int i = 0, mx = -1; i < n; i++){
mx = max(mx, p[i]);
if (mx <= i) cycleend[i] = 1;
}
vector<int> cur, used(n), cid(n), minpos(n, INF), maxpos(n, -1);
vector<int> minl(n, INF), maxr(n, -1);
vector<vector<int>> has(n);
int id = 0;
function<void(int)> dfs = [&] (int v){
used[v] = 1, cid[v] = id;
minpos[id] = min(minpos[id], v);
maxpos[id] = max(maxpos[id], v);
has[id].pb(v);
if (!used[p[v]]) dfs(p[v]);
};
for (int i = 0; i < n; i++){
if (used[i]) continue;
dfs(i);
id++;
}
vector<int> order(id);
iota(all(order), 0);
sort(all(order), [&] (int i, int j){
return minpos[i] < minpos[j];
});
for (int i = 0; i < 4 * n; i++) t[i] = INF;
for (auto i : order){
minl[i] = min(minpos[i], query(0, 0, n - 1, minpos[i], maxpos[i]));
for (auto v : has[i]) modify(0, 0, n - 1, v, minl[i]);
}
sort(all(order), [&] (int i, int j){
return maxpos[i] > maxpos[j];
});
for (int i = 0; i < 4 * n; i++) t[i] = INF;
for (auto i : order){
maxr[i] = max(maxpos[i], -query(0, 0, n - 1, minpos[i], maxpos[i]));
for (auto v : has[i]) modify(0, 0, n - 1, v, -maxr[i]);
}
int startl = s, startr = s;
while (startl > 0 && !cycleend[startl - 1]) startl--;
while (!cycleend[startr]) startr++;
vector<int> ids;
for (int i = 0; i < id; i++) if (minl[i] <= s && maxr[i] >= maxr[cid[s]]) ids.pb(i);
sort(all(ids), [&] (int i, int j){
return maxr[i] < maxr[j];
});
ll ans1 = 0;
for (int i = 1; i < sz(ids); i++){
int l = minl[ids[i - 1]], cur1 = 0;
while (l > minl[ids[i]]) l--, l = minl[cid[l]], cur1++;
int r = maxr[ids[i - 1]], cur2 = 0;
while (r < maxr[ids[i]]) r++, r = maxr[cid[r]], cur2++;
ans1 += min(cur1, cur2);
}
return ans + 2 * ans1;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
0 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 |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
280 KB |
Output is correct |
16 |
Correct |
0 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 |
0 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 |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
280 KB |
Output is correct |
16 |
Correct |
0 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 |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 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 |
0 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 |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
280 KB |
Output is correct |
16 |
Correct |
0 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 |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
488 ms |
100080 KB |
Output is correct |
31 |
Correct |
588 ms |
87796 KB |
Output is correct |
32 |
Correct |
82 ms |
8052 KB |
Output is correct |
33 |
Correct |
78 ms |
8064 KB |
Output is correct |
34 |
Correct |
76 ms |
8056 KB |
Output is correct |
35 |
Correct |
472 ms |
90748 KB |
Output is correct |
36 |
Correct |
389 ms |
82452 KB |
Output is correct |
37 |
Correct |
318 ms |
77180 KB |
Output is correct |
38 |
Correct |
319 ms |
76748 KB |
Output is correct |
39 |
Correct |
325 ms |
76672 KB |
Output is correct |
40 |
Correct |
352 ms |
76796 KB |
Output is correct |
41 |
Correct |
425 ms |
85892 KB |
Output is correct |
42 |
Correct |
395 ms |
80196 KB |
Output is correct |
43 |
Correct |
583 ms |
97144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 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 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
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 |
0 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 |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
280 KB |
Output is correct |
16 |
Correct |
0 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 |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
488 ms |
100080 KB |
Output is correct |
31 |
Correct |
588 ms |
87796 KB |
Output is correct |
32 |
Correct |
82 ms |
8052 KB |
Output is correct |
33 |
Correct |
78 ms |
8064 KB |
Output is correct |
34 |
Correct |
76 ms |
8056 KB |
Output is correct |
35 |
Correct |
472 ms |
90748 KB |
Output is correct |
36 |
Correct |
389 ms |
82452 KB |
Output is correct |
37 |
Correct |
318 ms |
77180 KB |
Output is correct |
38 |
Correct |
319 ms |
76748 KB |
Output is correct |
39 |
Correct |
325 ms |
76672 KB |
Output is correct |
40 |
Correct |
352 ms |
76796 KB |
Output is correct |
41 |
Correct |
425 ms |
85892 KB |
Output is correct |
42 |
Correct |
395 ms |
80196 KB |
Output is correct |
43 |
Correct |
583 ms |
97144 KB |
Output is correct |
44 |
Correct |
1 ms |
340 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 |
Correct |
0 ms |
212 KB |
Output is correct |
54 |
Correct |
1 ms |
340 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
1 ms |
340 KB |
Output is correct |
57 |
Correct |
1 ms |
340 KB |
Output is correct |
58 |
Correct |
1 ms |
340 KB |
Output is correct |
59 |
Correct |
1 ms |
340 KB |
Output is correct |
60 |
Correct |
1 ms |
340 KB |
Output is correct |
61 |
Correct |
1 ms |
340 KB |
Output is correct |
62 |
Correct |
1 ms |
340 KB |
Output is correct |
63 |
Correct |
1 ms |
340 KB |
Output is correct |
64 |
Correct |
561 ms |
97824 KB |
Output is correct |
65 |
Correct |
538 ms |
100248 KB |
Output is correct |
66 |
Correct |
337 ms |
77984 KB |
Output is correct |
67 |
Correct |
326 ms |
77516 KB |
Output is correct |
68 |
Correct |
41 ms |
9172 KB |
Output is correct |
69 |
Correct |
32 ms |
8828 KB |
Output is correct |
70 |
Correct |
38 ms |
9400 KB |
Output is correct |
71 |
Correct |
45 ms |
10288 KB |
Output is correct |
72 |
Correct |
49 ms |
10888 KB |
Output is correct |
73 |
Correct |
32 ms |
8660 KB |
Output is correct |
74 |
Correct |
511 ms |
96216 KB |
Output is correct |
75 |
Correct |
520 ms |
96240 KB |
Output is correct |
76 |
Correct |
557 ms |
97452 KB |
Output is correct |
77 |
Correct |
606 ms |
97700 KB |
Output is correct |
78 |
Correct |
549 ms |
93980 KB |
Output is correct |
79 |
Correct |
546 ms |
93928 KB |
Output is correct |
80 |
Correct |
76 ms |
8804 KB |
Output is correct |
81 |
Correct |
518 ms |
91428 KB |
Output is correct |
82 |
Correct |
516 ms |
91436 KB |
Output is correct |
83 |
Correct |
446 ms |
86164 KB |
Output is correct |
84 |
Correct |
410 ms |
84312 KB |
Output is correct |
85 |
Correct |
387 ms |
80088 KB |
Output is correct |
86 |
Correct |
328 ms |
78440 KB |
Output is correct |
87 |
Correct |
614 ms |
102604 KB |
Output is correct |
88 |
Correct |
557 ms |
97108 KB |
Output is correct |
89 |
Correct |
465 ms |
88768 KB |
Output is correct |
90 |
Correct |
321 ms |
77804 KB |
Output is correct |
91 |
Correct |
321 ms |
77136 KB |
Output is correct |
92 |
Correct |
351 ms |
76948 KB |
Output is correct |