#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
vi a,vis,arr;
void dfs(int x){
arr.PB(x);
vis[x]=1;
if(vis[a[x]]==0)dfs(a[x]);
}
long long minimum_walk(std::vector<int> p, int s) {
a=p;
while(a.size()&&a[a.back()]==a.back())a.pop_back();
if(a.size()==0)return 0;
int n=a.size();
vis.resize(n,0);
int pos=0;
while(pos<n&&a[pos]==pos)pos++;
ll ans=0;
if(s>=n){
ans=(s-n+1)*2LL;
s=n-1;
}
if(s<pos){
ans=(pos-s)*2LL;
s=pos;
}
vector<pi> c(n,{-1,-1});
REP(i,pos,n)if(!vis[i]&&i!=a[i]){
arr.clear();
dfs(i);
sort(all(arr));
for(auto u:arr)ans+=(ll)abs(u-a[u]);
for(auto u:arr)c[u]={arr[0],arr.back()};
}
int l=s,r=s;
queue<int> L,R;
if(c[s].F!=-1)L.push(s);
ll cl=0,cr=0;
while(!L.empty()){
int x=L.front();
L.pop();
if(c[x].F<=l&&c[x].S>=r){
ans+=cl;
cl=0;cr=0;
}
REP(i,c[x].F,l)if(c[i].F!=-1)L.push(i);
REP(i,r+1,c[x].S+1)if(c[i].F!=-1)L.push(i);
l=min(l,c[x].F);
r=max(r,c[x].S);
}
while(l!=pos||r!=n-1){
if(l!=pos){
l--;
if(c[l].F!=-1)L.push(l);
cl+=2;
}
if(r!=n-1){
r++;
if(c[r].F!=-1)R.push(r);
cr+=2;
}
int lt=l,rt=r;
l=n;r=-1;
while(!L.empty()){
int x=L.front();
L.pop();
REP(i,c[x].F,min(l,lt))if(c[i].F!=-1)L.push(i);
REP(i,max(r,rt)+1,c[x].S+1)if(c[i].F!=-1)L.push(i);
l=min(l,c[x].F);
r=max(r,c[x].S);
}
if(l<=lt&&r>=rt){
ans+=cl;
cl=0;cr=0;
}
while(!R.empty()){
int x=R.front();
R.pop();
REP(i,c[x].F,min(l,lt))if(c[i].F!=-1)R.push(i);
REP(i,max(r,rt)+1,c[x].S+1)if(c[i].F!=-1)R.push(i);
l=min(l,c[x].F);
r=max(r,c[x].S);
}
if(l<=lt&&r>=rt){
ans+=cr;
cl=0;cr=0;
}
l=min(l,lt);
r=max(r,rt);
}
return ans+cl+cr;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |