#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, INF = 1e9;
int p[maxn], vis[maxn];
vector<pair<int,int>> vec = {{-1, -1}};
int minimum_walk(vector<int32_t> P, int32_t s) {
int n = P.size();
for (int i=0;i<n;i++) p[i] = P[i];
for (int i=0;i<n;i++) vis[i] = 0;
int ans = 0, cnt = 0;
for (int i=0;i<n;i++) if (!vis[i]) {
if (p[i]==i && i==s) {
cnt++;
vis[i] = cnt;
vec.push_back({s, s});
}
if (p[i]==i) continue;
int u = i;
pair<int,int> val = {u, u};
cnt++;
while (true) {
vis[u] = cnt;
val.first = min(u, val.first);
val.second = max(u, val.second);
int v = p[u];
ans += abs(v-u);
if (v==i) break;
u = v;
}
vec.push_back(val);
}
sort(vec.begin(), vec.end());
int lastl = vec[1].first, mx = vec[1].second;
int LL = -1, RR = -1;
for (int i=2;i<vec.size();i++) {
if (vec[i].first > mx) {
if (lastl<=s && s<=mx) {
LL = lastl, RR = mx;
}
lastl = vec[i].first;
ans += (vec[i].first - mx)*2;
}
mx = max(vec[i].second, mx);
}
if (L == -1) LL = lastl, RR = mx;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, vis[s]});
int dist[cnt+5];
for (int i=1;i<=cnt;i++) dist[i] = -1;
while (pq.size() > 0) {
int u = pq.top().second, d = pq.top().first;
pq.pop();
if (vec[u].second < LL || vec[u].first > RR) dist[u] = -2;
if (dist[u]!=-1) continue;
dist[u] = d;
for (int i=vec[u].first; i<=vec[u].second;i++) {
if (p[i]!=i && dist[vis[i]]==-1) pq.push({d, vis[i]});
}
for (int i=vec[u].first-1;i>=LL;i--) {
if (p[i]!=i) {
if (dist[vis[i]]==-1) pq.push({d + (vec[u].first - i)*2, vis[i]});
}
}
for (int i=vec[u].second+1;i<=RR;i++) {
if (p[i]!=i) {
if (dist[vis[i]]==-1) pq.push({d + (i - vec[u].first)*2, vis[i]});
}
}
}
for (int i=1;i<=cnt;i++) assert((dist[i]==-1) == (vec[i].first>RR || vec[i].second<LL));
int MX = 0;
for (int i=1;i<=cnt;i++) if (dist[i]!=-1) MX = max(dist[i], MX);
ans += MX;
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int32_t)':
books.cpp:39:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i=2;i<vec.size();i++) {
| ~^~~~~~~~~~~
books.cpp:49:9: error: 'L' was not declared in this scope; did you mean 'LL'?
49 | if (L == -1) LL = lastl, RR = mx;
| ^
| LL
