This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int n;
const int N = (int)1e6 + 100;
int lef[N], rig[N];
bool vis[N];
bool has[N];
int tl, tr;
void extend(int &li, int &ri){
int ni = min(lef[li],lef[ri]);
int nj = max(rig[li],rig[ri]);
while(li > ni || ri < nj){
if(li > ni){
li--;
ni = min(ni, lef[li]);
nj = max(nj, rig[li]);
}
else{
ri++;
ni = min(ni, lef[ri]);
nj = max(nj, rig[ri]);
}
}
}
int disl[N];
int disr[N];
int solve(int li, int ri){
int cnt = 0;
extend(li, ri);
while(li != tl || ri != tr){
if(li == tl){
cnt += 2;
ri ++ ;
}
else if(ri == tr){
cnt += 2;
li -- ;
}
else{
if(li > tl && disl[li-1] < disr[ri+1]){
li -- ;
cnt += 2;
}
else{
ri ++ ;
cnt += 2;
}
}
extend(li,ri);
}
return cnt;
}
long long minimum_walk(vector<int> p, int s) {
n = p.size();
int id;
int low, high;
ll sol = 0;
tl = tr = s;
for(int i = 0 ; i < n; i ++ ){
sol += abs(p[i] - i);
if(!vis[i]){
vector<int> cyc;
id = i;
while(!vis[id]){
vis[id]=true;
cyc.push_back(id);
id=p[id];
}
low = n-1;
high = 0;
for(auto x : cyc){
low = min(low, x);
high = max(high, x);
}
for(auto x : cyc){
lef[x] = low;
rig[x] = high;
}
}
if(p[i] != i){
tl = min(tl, i);
tr = max(tr, i);
}
}
for(int i = 0 ; i < n; i ++ ){
disl[i] = (int)1e9;
if(rig[i] >= s)
disl[i]=0;
else{
if(lef[i] == i){
if(i>0)disl[i]=disl[i-1]+2;
}
else{
disl[i]=min(disl[i],disl[i-1]);
disl[i]=min(disl[i],disl[lef[i]]);
}
}
}
for(int i = n - 1; i >= 0 ; i -- ){
disr[i]=(int)1e9;
if(lef[i] <= s)
disr[i]=0;
else{
if(rig[i] == i){
if(i+1<n) disr[i]=disr[i+1]+2;
}
else{
disr[i]=min(disr[i],disr[i+1]);
disr[i]=min(disr[i],disr[rig[i]]);
}
}
}
return sol + solve(s, s);
}
# | 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... |