#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4000050,M=1000050;
int n,pt,cmx,st,vis[M],par[M],mx[M],mn[M],rrl[M],dist[5][N],lb,rb;
ll ans=LLONG_MAX,cyc;
queue<int> curr[N];
vector<pair<int,int>> adj[2][N];
void addedge(int u,int v,int w){
adj[0][u].push_back({v,w});
adj[1][v].push_back({u,w});
}
void build(int id,int l,int r){
if (l==r){
rrl[l]=id;
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
addedge(id,id*2,0);
addedge(id,id*2+1,0);
}
void modify(int id,int l,int r,int ql,int qr,int v){
if (l>qr||r<ql) return;
if (l>=ql&&r<=qr){
addedge(v,id,0);
return;
}
int m=(l+r)/2;
modify(id*2,l,m,ql,qr,v);
modify(id*2+1,m+1,r,ql,qr,v);
}
void bfs(int s,int id,int sav){
for (int i=0;i<N;i++) dist[sav][i]=N<<2;
dist[sav][s]=0; curr[0].push(s);
for (int i=0;i<N;i++){
while (curr[i].size()){
int cnde=curr[i].front();
curr[i].pop();
for (auto j:adj[id][cnde]) if (dist[sav][cnde]+j.second<dist[sav][j.first]){
dist[sav][j.first]=dist[sav][cnde]+j.second;
curr[dist[sav][j.first]].push(j.first);
}
}
}
}
ll minimum_walk(vector<int> p, int s) {
n=p.size();
for (int i=0;i<n;i++){
if (vis[i]) continue;
par[i]=i; vis[i]=1; mx[i]=mn[i]=i; cyc+=abs(i-p[i]);
for (int j=p[i];j!=i;j=p[j]) mx[i]=max(mx[i],j),mn[i]=min(mn[i],j),vis[j]=1,par[j]=i,cyc+=abs(j-p[j]);
}
//for (int i=0;i<n;i++) cout<<i<<": "<<par[i]<<" "<<mx[i]<<" "<<sz[i]<<"\n";
memset(vis,0,sizeof(vis));
build(1,0,n-1);
for (int i=1;i<=s;i++) addedge(rrl[i],rrl[i-1],1);
for (int i=s+1;i<n;i++) addedge(rrl[i-1],rrl[i],1);
for (int i=0;i<n;i++) modify(1,0,n-1,mn[i],mx[i],rrl[i]);
lb=0,rb=n-1;
while (p[lb]==lb&&lb<s) lb++;
while (p[rb]==rb&&rb>s) rb--;
bfs(rrl[s],0,0);
bfs(rrl[lb],1,1);
bfs(rrl[rb],1,2);
for (int i=0;i<N;i++) ans=min(ans,(ll)dist[0][i]+dist[1][i]+dist[2][i]);
return cyc+ans*2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
511 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
511 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
511 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
511 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |