#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
inline bool smin(int &a, int b) { return b < a ? a = b, true : false; }
inline bool smax(int &a, int b) { return a < b ? a = b, true : false; }
const int N = 1e6 + 10;
int A[N], B[N], n;
int A_[N << 1], B_[N << 1];
#define lid i << 1
#define rid lid | 1
inline int getMin(int l, int r) {
int res = l;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) smin(res, B_[l++]);
if (r & 1) smin(res, B_[--r]);
}
return res;
}
inline int getMax(int l, int r) {
int res = r;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) smax(res, A_[l++]);
if (r & 1) smax(res, A_[--r]);
}
return res;
}
inline void build() {
rep(i, 0, n) {
A_[i + n] = A[i];
B_[i + n] = B[i];
}
for (int i = n - 1; i; i--) {
A_[i] = max(A_[lid], A_[rid]);
B_[i] = min(B_[lid], B_[rid]);
}
}
map<pii, pii> mp;
pii extend(int l, int r) {
if (mp.count({l, r})) return mp[{l, r}];
int newL = getMin(l, r);
int newR = getMax(l, r);
if (newL < l || r < newR) return mp[{l, r}] = extend(newL, newR);
return mp[{l, r}] = {l, r};
}
ll minimum_walk(vi p, int s) {
n = p.size();
fill(A, A + n, -1);
fill(B, B + n, n);
ll res = 0;
int l2 = s, r2 = s;
rep(i, 0, n) {
res += abs(i - p[i]);
int a = min(i, p[i]);
int b = i ^ p[i] ^ a;
A[a] = b;
B[b] = a;
if (a != b) {
smin(l2, a);
smax(r2, b);
}
}
build();
int l = s, r = s;
tie(l, r) = extend(l, r);
while (l != l2 && r != r2) {
int l0 = l, r0 = r, l1 = l, r1 = r, aa = 0, bb = 0;
while (true) {
int lp = l0, rp = r0;
tie(l0, r0) = extend(l0 - 1, r0);
aa += 2;
if (rp != r0 || l0 == l2) break;
}
while (true) {
int lp = l1, rp = r1;
tie(l1, r1) = extend(l1, r1 + 1);
bb += 2;
if (lp != l1 || r1 == r2) break;
}
if (r0 == r || l1 == l) {
res += aa + bb;
l = l2, r = r2;
break;
}
res += min(aa, bb);
l = l0, r = r0;
}
while (l != l2) {
res += 2;
tie(l, r) = extend(l - 1, r);
}
while (r != r2) {
res += 2;
tie(l, r) = extend(l, r + 1);
}
return res;
}
Compilation message
books.cpp: In function 'll minimum_walk(vi, int)':
books.cpp:91:11: warning: unused variable 'lp' [-Wunused-variable]
int lp = l0, rp = r0;
^~
books.cpp:97:20: warning: unused variable 'rp' [-Wunused-variable]
int lp = l1, rp = r1;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
396 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
396 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
396 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
219 ms |
38392 KB |
Output is correct |
31 |
Correct |
223 ms |
38460 KB |
Output is correct |
32 |
Correct |
177 ms |
38316 KB |
Output is correct |
33 |
Correct |
671 ms |
92792 KB |
Output is correct |
34 |
Correct |
658 ms |
92792 KB |
Output is correct |
35 |
Correct |
571 ms |
83404 KB |
Output is correct |
36 |
Correct |
336 ms |
57336 KB |
Output is correct |
37 |
Correct |
183 ms |
39800 KB |
Output is correct |
38 |
Correct |
178 ms |
38616 KB |
Output is correct |
39 |
Correct |
191 ms |
38648 KB |
Output is correct |
40 |
Correct |
182 ms |
38392 KB |
Output is correct |
41 |
Correct |
212 ms |
38392 KB |
Output is correct |
42 |
Correct |
202 ms |
38316 KB |
Output is correct |
43 |
Correct |
168 ms |
38392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
504 KB |
Output is correct |
12 |
Correct |
3 ms |
504 KB |
Output is correct |
13 |
Correct |
3 ms |
396 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
508 KB |
Output is correct |
18 |
Correct |
3 ms |
380 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
13 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
396 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
2 ms |
504 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
219 ms |
38392 KB |
Output is correct |
31 |
Correct |
223 ms |
38460 KB |
Output is correct |
32 |
Correct |
177 ms |
38316 KB |
Output is correct |
33 |
Correct |
671 ms |
92792 KB |
Output is correct |
34 |
Correct |
658 ms |
92792 KB |
Output is correct |
35 |
Correct |
571 ms |
83404 KB |
Output is correct |
36 |
Correct |
336 ms |
57336 KB |
Output is correct |
37 |
Correct |
183 ms |
39800 KB |
Output is correct |
38 |
Correct |
178 ms |
38616 KB |
Output is correct |
39 |
Correct |
191 ms |
38648 KB |
Output is correct |
40 |
Correct |
182 ms |
38392 KB |
Output is correct |
41 |
Correct |
212 ms |
38392 KB |
Output is correct |
42 |
Correct |
202 ms |
38316 KB |
Output is correct |
43 |
Correct |
168 ms |
38392 KB |
Output is correct |
44 |
Correct |
3 ms |
376 KB |
Output is correct |
45 |
Correct |
3 ms |
376 KB |
Output is correct |
46 |
Correct |
3 ms |
376 KB |
Output is correct |
47 |
Correct |
2 ms |
376 KB |
Output is correct |
48 |
Correct |
2 ms |
376 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
2 ms |
376 KB |
Output is correct |
52 |
Correct |
2 ms |
376 KB |
Output is correct |
53 |
Correct |
2 ms |
376 KB |
Output is correct |
54 |
Correct |
3 ms |
504 KB |
Output is correct |
55 |
Correct |
3 ms |
504 KB |
Output is correct |
56 |
Correct |
3 ms |
396 KB |
Output is correct |
57 |
Correct |
3 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
504 KB |
Output is correct |
59 |
Correct |
2 ms |
376 KB |
Output is correct |
60 |
Correct |
3 ms |
508 KB |
Output is correct |
61 |
Correct |
3 ms |
380 KB |
Output is correct |
62 |
Correct |
2 ms |
376 KB |
Output is correct |
63 |
Correct |
13 ms |
376 KB |
Output is correct |
64 |
Correct |
191 ms |
39360 KB |
Output is correct |
65 |
Correct |
189 ms |
40056 KB |
Output is correct |
66 |
Correct |
173 ms |
38396 KB |
Output is correct |
67 |
Correct |
185 ms |
38448 KB |
Output is correct |
68 |
Correct |
18 ms |
4084 KB |
Output is correct |
69 |
Correct |
18 ms |
4088 KB |
Output is correct |
70 |
Correct |
18 ms |
4088 KB |
Output is correct |
71 |
Correct |
18 ms |
4088 KB |
Output is correct |
72 |
Correct |
19 ms |
4344 KB |
Output is correct |
73 |
Correct |
21 ms |
4088 KB |
Output is correct |
74 |
Correct |
653 ms |
92792 KB |
Output is correct |
75 |
Correct |
676 ms |
92764 KB |
Output is correct |
76 |
Correct |
170 ms |
38392 KB |
Output is correct |
77 |
Correct |
188 ms |
38520 KB |
Output is correct |
78 |
Correct |
179 ms |
38448 KB |
Output is correct |
79 |
Correct |
180 ms |
38392 KB |
Output is correct |
80 |
Correct |
162 ms |
38316 KB |
Output is correct |
81 |
Correct |
1602 ms |
121936 KB |
Output is correct |
82 |
Correct |
1680 ms |
121920 KB |
Output is correct |
83 |
Correct |
503 ms |
73796 KB |
Output is correct |
84 |
Correct |
421 ms |
63868 KB |
Output is correct |
85 |
Correct |
251 ms |
47072 KB |
Output is correct |
86 |
Correct |
195 ms |
40956 KB |
Output is correct |
87 |
Correct |
936 ms |
110672 KB |
Output is correct |
88 |
Correct |
805 ms |
106792 KB |
Output is correct |
89 |
Correct |
610 ms |
84344 KB |
Output is correct |
90 |
Correct |
179 ms |
39132 KB |
Output is correct |
91 |
Correct |
185 ms |
38628 KB |
Output is correct |
92 |
Correct |
179 ms |
38392 KB |
Output is correct |