#include "books.h"
#include <string.h>
using namespace std;
const int N = 1000000;
const int INF = 0x3f3f3f3f;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
typedef vector<int> vi;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
char visited[N]; int xx[N], ll[N], rr[N], ll_[N], rr_[N], ii[N], m;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ll_[ii[j]] - ll_[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long minimum_walk(vi pp, int s) {
int n = pp.size(), h, i, j, l, r, l_, r_, cnt;
long long ans;
ans = 0;
for (i = 0; i < n; i++) {
if (i < pp[i])
ans += pp[i] - i;
else if (i > pp[i])
ans += i - pp[i];
if (!visited[i]) {
l_ = -INF, r_ = INF, l = INF, r = -INF;
while (!visited[i]) {
l = min(l, i), r = max(r, i);
if (i <= s)
l_ = max(l_, i);
if (i >= s)
r_ = min(r_, i);
visited[i] = 1, i = pp[i];
}
xx[l]++, xx[r]--;
if (l <= s && s <= r)
ll_[m] = l_, rr_[m] = r_, ll[m] = l, rr[m] = r, ii[m] = i, m++;
}
}
for (i = 1; i < n - 1; i++)
xx[i] += xx[i - 1];
for (i = n - 1; i > 0; i--)
xx[i] = xx[i - 1] == 0;
for (i = 1; i < n; i++)
xx[i] += xx[i - 1];
sort(ii, 0, m);
cnt = 0;
for (h = 0; h < m; h++) {
i = ii[h];
while (cnt && rr_[ii[cnt - 1]] < rr_[i]) {
j = ii[--cnt];
ll_[i] = max(ll_[i], ll_[j]), rr_[i] = min(rr_[i], rr_[j]);
ll[i] = min(ll[i], ll[j]), rr[i] = max(rr[i], rr[j]);
}
ii[cnt++] = i;
}
for (h = cnt - 1, l_ = s, r_ = s; h >= 0; h--) {
i = ii[h];
if (l_ > ll_[i] && r_ < rr_[i])
ans += min(xx[l_] - xx[ll_[i]], xx[rr_[i]] - xx[r_]) * 2;
l_ = min(l_, ll[i]), r_ = max(r_, rr[i]);
}
i = 0;
while (i < l_ && pp[i] == i)
i++;
j = n - 1;
while (j > r_ && pp[j] == j)
j--;
ans += (xx[l_] - xx[i] + xx[j] - xx[r_]) * 2;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
332 KB |
Output is correct |
| 14 |
Correct |
0 ms |
332 KB |
Output is correct |
| 15 |
Correct |
0 ms |
332 KB |
Output is correct |
| 16 |
Correct |
0 ms |
332 KB |
Output is correct |
| 17 |
Correct |
0 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
332 KB |
Output is correct |
| 14 |
Correct |
0 ms |
332 KB |
Output is correct |
| 15 |
Correct |
0 ms |
332 KB |
Output is correct |
| 16 |
Correct |
0 ms |
332 KB |
Output is correct |
| 17 |
Correct |
0 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
332 KB |
Output is correct |
| 14 |
Correct |
0 ms |
332 KB |
Output is correct |
| 15 |
Correct |
0 ms |
332 KB |
Output is correct |
| 16 |
Correct |
0 ms |
332 KB |
Output is correct |
| 17 |
Correct |
0 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
172 ms |
13028 KB |
Output is correct |
| 31 |
Correct |
193 ms |
13036 KB |
Output is correct |
| 32 |
Correct |
140 ms |
12996 KB |
Output is correct |
| 33 |
Correct |
144 ms |
12912 KB |
Output is correct |
| 34 |
Correct |
143 ms |
13024 KB |
Output is correct |
| 35 |
Correct |
148 ms |
13124 KB |
Output is correct |
| 36 |
Correct |
157 ms |
13028 KB |
Output is correct |
| 37 |
Correct |
146 ms |
13028 KB |
Output is correct |
| 38 |
Correct |
145 ms |
13028 KB |
Output is correct |
| 39 |
Correct |
144 ms |
12912 KB |
Output is correct |
| 40 |
Correct |
151 ms |
13064 KB |
Output is correct |
| 41 |
Correct |
175 ms |
13028 KB |
Output is correct |
| 42 |
Correct |
157 ms |
13032 KB |
Output is correct |
| 43 |
Correct |
167 ms |
13124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
332 KB |
Output is correct |
| 13 |
Correct |
0 ms |
332 KB |
Output is correct |
| 14 |
Correct |
0 ms |
332 KB |
Output is correct |
| 15 |
Correct |
0 ms |
332 KB |
Output is correct |
| 16 |
Correct |
0 ms |
332 KB |
Output is correct |
| 17 |
Correct |
0 ms |
332 KB |
Output is correct |
| 18 |
Correct |
0 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
172 ms |
13028 KB |
Output is correct |
| 31 |
Correct |
193 ms |
13036 KB |
Output is correct |
| 32 |
Correct |
140 ms |
12996 KB |
Output is correct |
| 33 |
Correct |
144 ms |
12912 KB |
Output is correct |
| 34 |
Correct |
143 ms |
13024 KB |
Output is correct |
| 35 |
Correct |
148 ms |
13124 KB |
Output is correct |
| 36 |
Correct |
157 ms |
13028 KB |
Output is correct |
| 37 |
Correct |
146 ms |
13028 KB |
Output is correct |
| 38 |
Correct |
145 ms |
13028 KB |
Output is correct |
| 39 |
Correct |
144 ms |
12912 KB |
Output is correct |
| 40 |
Correct |
151 ms |
13064 KB |
Output is correct |
| 41 |
Correct |
175 ms |
13028 KB |
Output is correct |
| 42 |
Correct |
157 ms |
13032 KB |
Output is correct |
| 43 |
Correct |
167 ms |
13124 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
332 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 45 |
Halted |
0 ms |
0 KB |
- |
