#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "books.h"
struct Minimum_Fenwick_Tree
{
int bit[N],d[N];
void Init()
{
memset(bit,63,sizeof(bit));
memset(d,63,sizeof(d));
}
void update(int i,int k)
{
d[i]=min(d[i],k);
while(i<N) bit[i]=min(bit[i],k),i+=(i & -i);
}
int get(int l,int r)
{
int res=1e9,i=r;
while(i>=l)
if(i-(i & -i)>=l) res=min(res,bit[i]),i-=(i & -i);
else res=min(res,d[i]),i--;
return res;
}
} FT_mi;
struct Maximum_Fenwick_Tree
{
int bit[N],d[N];
void update(int i,int k)
{
d[i]=max(d[i],k);
while(i<N) bit[i]=max(bit[i],k),i+=(i & -i);
}
int get(int l,int r)
{
int res=0,i=r;
while(i>=l)
if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
else res=max(res,d[i]),i--;
return res;
}
} FT_ma,FT_done;
int n,i,j,k,pos,p[N],n_cycle,n_node,n_point,in[N],par[N];
vector <int> a[N];
II seg_node[N],seg_cycle[N],point[2*N];
ll minimum_walk(vector <int> _p,int s)
{
s++;
for(int k:_p) p[++n]=k,p[n]++;
//Build cycle
for(i=1;i<=n;i++)
if(in[i]==0)
{
n_cycle++;
int l=1e9,r=0;
for(j=i;in[j]==0;j=p[j])
{
l=min(l,j);
r=max(r,j);
in[j]=n_cycle;
}
seg_cycle[n_cycle]={ l,r };
}
FT_mi.Init();
for(i=1;i<=n;i++)
{
FT_mi.update(i,seg_cycle[in[i]].fst);
FT_ma.update(i,seg_cycle[in[i]].snd);
}
sort(seg_cycle+1,seg_cycle+n_cycle+1,[&](II a,II b){ return a.snd<b.snd; });
//Build extend segment
for(i=1;i<=n_cycle;i++)
{
int l=seg_cycle[i].fst,r=seg_cycle[i].snd;
if(FT_done.get(1,l)>=r) continue;
while(1)
{
int k;
if((k=FT_mi.get(l,r))<l) l=k;
else if((k=FT_ma.get(l,r))>r) r=k;
else break;
}
FT_done.update(l,r);
point[++n_point]={ l,0 };
point[++n_point]={ r,1 };
}
sort(point+1,point+n_point+1);
//Build Tree of extend segment
stack <II> st;
for(i=1;i<=n_point;i++)
if(point[i].snd==0) st.push(point[i]);
else
{
n_node++;
while(st.top().snd==1)
{
int u=st.top().fst;
a[n_node].push_back(u);
par[u]=n_node;
st.pop();
}
seg_node[n_node]={ st.top().fst,point[i].fst };
reverse(a[n_node].begin(),a[n_node].end());
st.pop();
st.push({ n_node,1 });
}
//Init move
int Begin=0,End=0;
ll res=0;
for(i=1;i<=n;i++)
{
res+=abs(i-p[i]);
if(i!=p[i])
{
if(Begin==0) Begin=i;
End=i;
}
}
if(Begin==0) return 0;
Begin=min(Begin,s);
End=max(End,s);
for(i=1;i<=n_node;i++)
{
if(seg_node[i].fst>=Begin && seg_node[i].snd<=End && par[i]==0)
res+=2;
}
res-=2;
for(i=1;i<=n_node;i++)
if(seg_node[i].fst<=s && s<=seg_node[i].snd && a[i].size()==0)
break;
while(par[i]>0)
{
j=par[i];
ll cl=0,cr=0;
for(pos=0;pos<a[j].size();pos++)
if(a[j][pos]==i) break;
for(k=pos;k>=0;k--)
{
cl++;
if(k>0 && seg_node[a[j][k]].fst-seg_node[a[j][k-1]].snd>1) break;
}
for(k=pos+1;k<a[j].size();j++)
{
cr++;
if(k<a[j].size()-1 && seg_node[a[j][k+1]].fst-seg_node[a[j][k]].snd>1) break;
}
res+=2*min(cl,cr);
i=j;
}
return res;
}
int main()
{
freopen("books.inp","r",stdin);
freopen("books.out","w",stdout);
vector <int> p;
int n,s,k;
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>k,p.push_back(k);
cout<<minimum_walk(p,s);
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(pos=0;pos<a[j].size();pos++)
| ~~~^~~~~~~~~~~~
books.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(k=pos+1;k<a[j].size();j++)
| ~^~~~~~~~~~~~
books.cpp:172:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if(k<a[j].size()-1 && seg_node[a[j][k+1]].fst-seg_node[a[j][k]].snd>1) break;
| ~^~~~~~~~~~~~~~
books.cpp: In function 'int main()':
books.cpp:182:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | freopen("books.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
books.cpp:183:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | freopen("books.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccysRjzD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3EIEED.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
