//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#include "books.h"
const int inf = 1e9;
pii ran[maxn], color[maxn];
long long minimum_walk(vector<int> p, int s) {
vector<int> a(n, 0);
vector<bool> vis(n);
ll ans = 0;
int n = p.size();
{
int c = 0;
for (int i = 0;i < n;i++) {
ans += abs(p[i] - i);
if (!vis[i]) {
c++;
int cur = i;
int mi = inf, ma = 0;
do {
mi = min(mi, cur);
ma = max(ma, cur);
a[cur] = c;
vis[cur] = 1;
cur = p[cur];
} while (!vis[cur]);
color[c] = {mi, ma};
}
}
for (int i = 0;i < n;i++) ran[i] = color[a[i]];
}
int lb = 0, rb = n-1;
while (lb < s && p[lb] == lb) lb++;
while (rb > s && p[rb] == rb) rb--;
auto expand = [&] (int l, int r, int nl, int nr, int type) { //0:none, 1:left, 2:right
if (type == 1) {
l = max(lb, l-1);
nl = min(nl, ran[l].ff);
nr = max(nr, ran[l].ss);
} else if(type == 2) {
r = min(rb, r+1);
nl = min(nl, ran[r].ff);
nr = max(nr, ran[r].ss);
}
while (nl < l || nr > r) {
int tl = nl, tr = nr;
while (tl < l) {
l--;
nl = min(nl, ran[l].ff);
nr = max(nr, ran[l].ss);
}
while (tr > r) {
r++;
nl = min(nl, ran[r].ff);
nr = max(nr, ran[r].ss);
}
}
return make_pair(l, r);
};
pii cur = {s, s};
cur = expand(s, s, ran[s].ff, ran[s].ss, 0);
while (cur.ff > lb || cur.ss < rb) {
if (cur.ff == lb) {
cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 2);
ans+=2;
} else if (cur.ss == rb){
cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 1);
ans+=2;
} else {
pii tmp = cur, lef;
int sl = 0, sr = 0, vl, vr;
while (tmp.ss <= cur.ss) {
tmp = expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 1);
sl++;
if (tmp.ff == lb) break;
}
vl = sl;
if (tmp.ss <= cur.ss) vl = inf;
lef = tmp;
tmp = cur;
while (tmp.ff >= cur.ff) {
tmp = expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 2);
sr++;
if (tmp.ss == rb) break;
}
vr = sr;
if (tmp.ff >= cur.ff) vr = inf;
if (vl == inf && vr == inf) {
ans += 2 * (sl + sr);
break;
} else if (vl < vr) {
ans += 2 * vl;
cur = lef;
} else {
ans += 2 * vr;
cur = tmp;
}
}
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:26:16: error: 'n' was not declared in this scope
26 | vector<int> a(n, 0);
| ^
