#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#include "grader.cpp"
#else
#include "books.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int INF = 1e9;
const int SIZE = 1e6 + 5;
int n, L, R;
int p[SIZE];
bool vs[SIZE];
int l[SIZE], r[SIZE];
int d[SIZE], in[SIZE], out[SIZE], dis[SIZE];
ll minimum_walk(vector<int> p_, int s) {
n = p_.size();
s++;
FOR (i, 1, n) {
p[i] = p_[i - 1] + 1;
in[i] = out[i] = vs[i] = 0;
}
FOR (i, 1, n) {
if (i < p[i]) {
out[i]++, out[p[i]]--;
in[i + 1]++, in[p[i] + 1]--;
d[i]++, d[p[i]]--;
} else {
out[p[i] + 1]++, out[i + 1]--;
in[p[i]]++, in[i]--;
d[p[i]]++, d[i]--;
}
}
FOR (i, 1, n) {
in[i] += in[i - 1];
out[i] += out[i - 1];
d[i] += d[i - 1];
}
L = 1, R = n;
while (R > s && d[R - 1] == 0) R--;
while (L < s && d[L] == 0) L++;
if (L == R) return 0;
FOR (i, L, R) if (vs[i] == 0) {
int mn = n, mx = 1, x = i;
vector<int> v;
while (vs[x] == 0) {
mn = min(mn, x);
mx = max(mx, x);
v.pb(x), vs[x] = 1, x = p[x];
}
for (int x : v) l[x] = mn, r[x] = mx;
}
FOR (i, L, R) {
int cl = l[i], cr = r[i];
FOR (j, l[i], r[i]) {
cl = min(cl, l[j]);
cr = max(cr, r[j]);
}
while (cl < l[i] || cr > r[i]) {
int ml = cl, mr = cr;
FOR (j, cl, l[i] - 1) {
ml = min(ml, l[j]);
mr = max(mr, r[j]);
}
FOR (j, r[i] + 1, cr) {
ml = min(ml, l[j]);
mr = max(mr, r[j]);
}
l[i] = cl, r[i] = cr;
cl = ml, cr = mr;
}
}
ll ans = 0;
FOR (i, L, R) ans += out[i];
FOR (i, L, R) dis[i] = INF, vs[i] = 0;
deque<int> q;
dis[s] = 0, q.pb(s);
while (q.size()) {
int pos = q.front();
q.pop_front();
if (vs[pos]) continue;
vs[pos] = 1;
auto upd = [&](int l, int r, int d, int t) {
FOR (i, l, r) if (d < dis[i]) {
dis[i] = d;
if (t == 0) q.emplace_front(i);
else q.pb(i);
}
};
upd(l[pos], r[pos], dis[pos], 0);
if (pos - 1 > L) upd(pos - 1, pos - 1, dis[pos] + 1, 1);
if (pos + 1 < R) upd(pos + 1, pos + 1, dis[pos] + 1, 1);
}
ans += 2 * *max_element(dis + L, dis + R + 1);
return ans;
}
/*
in1
4 0
0 2 3 1
out1
6
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12632 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
1 ms |
12636 KB |
Output is correct |
7 |
Correct |
1 ms |
12632 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
12736 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
1 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12632 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
1 ms |
12636 KB |
Output is correct |
7 |
Correct |
1 ms |
12632 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
12736 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
1 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
19 |
Correct |
2 ms |
12636 KB |
Output is correct |
20 |
Correct |
2 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
1 ms |
12636 KB |
Output is correct |
24 |
Correct |
1 ms |
12632 KB |
Output is correct |
25 |
Correct |
1 ms |
12636 KB |
Output is correct |
26 |
Correct |
1 ms |
12636 KB |
Output is correct |
27 |
Correct |
2 ms |
12632 KB |
Output is correct |
28 |
Correct |
1 ms |
12636 KB |
Output is correct |
29 |
Correct |
1 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12632 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
1 ms |
12636 KB |
Output is correct |
7 |
Correct |
1 ms |
12632 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
12736 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
1 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
19 |
Correct |
2 ms |
12636 KB |
Output is correct |
20 |
Correct |
2 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
1 ms |
12636 KB |
Output is correct |
24 |
Correct |
1 ms |
12632 KB |
Output is correct |
25 |
Correct |
1 ms |
12636 KB |
Output is correct |
26 |
Correct |
1 ms |
12636 KB |
Output is correct |
27 |
Correct |
2 ms |
12632 KB |
Output is correct |
28 |
Correct |
1 ms |
12636 KB |
Output is correct |
29 |
Correct |
1 ms |
12636 KB |
Output is correct |
30 |
Execution timed out |
2015 ms |
37568 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12636 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Incorrect |
1 ms |
12636 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '1592' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
12636 KB |
Output is correct |
2 |
Correct |
1 ms |
12632 KB |
Output is correct |
3 |
Correct |
1 ms |
12636 KB |
Output is correct |
4 |
Correct |
1 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
12636 KB |
Output is correct |
6 |
Correct |
1 ms |
12636 KB |
Output is correct |
7 |
Correct |
1 ms |
12632 KB |
Output is correct |
8 |
Correct |
1 ms |
12636 KB |
Output is correct |
9 |
Correct |
1 ms |
8540 KB |
Output is correct |
10 |
Correct |
1 ms |
12636 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
12636 KB |
Output is correct |
13 |
Correct |
1 ms |
12636 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
1 ms |
12736 KB |
Output is correct |
16 |
Correct |
1 ms |
12636 KB |
Output is correct |
17 |
Correct |
1 ms |
12636 KB |
Output is correct |
18 |
Correct |
1 ms |
12636 KB |
Output is correct |
19 |
Correct |
2 ms |
12636 KB |
Output is correct |
20 |
Correct |
2 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
8540 KB |
Output is correct |
22 |
Correct |
1 ms |
12636 KB |
Output is correct |
23 |
Correct |
1 ms |
12636 KB |
Output is correct |
24 |
Correct |
1 ms |
12632 KB |
Output is correct |
25 |
Correct |
1 ms |
12636 KB |
Output is correct |
26 |
Correct |
1 ms |
12636 KB |
Output is correct |
27 |
Correct |
2 ms |
12632 KB |
Output is correct |
28 |
Correct |
1 ms |
12636 KB |
Output is correct |
29 |
Correct |
1 ms |
12636 KB |
Output is correct |
30 |
Execution timed out |
2015 ms |
37568 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |