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>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e8;
//#include "books.h"
ll minimum_walk(vector<int> p, int s) {
ll N = p.size();
ll flux[N];
for (ll i=0;i<N;i++) {
flux[i]=0;
}
for (ll i=0;i<N;i++) {
if (p[i]>i) {
flux[i]++;
flux[p[i]]--;
}
}
ll pf[N+1];
pf[0]=0;
ll ans = 0;
for (ll i=0;i<N;i++) {
pf[i+1]=pf[i]+flux[i];
//cout << "x="<<(i+1)<<", pf[x]="<<pf[i+1]<<"\n";
if (pf[i+1]>1) {
ans += 2*(pf[i+1]-1);
}
}
ll maxl[N+1]; ll minl[N+1];
for (ll i=0;i<=N;i++) {
maxl[i]=-INF;
minl[i]=INF;
}
for (ll i=1;i<=N;i++) {
maxl[pf[i]]=max(maxl[pf[i]],i);
minl[pf[i]]=min(minl[pf[i]],i-1);
}
for (ll i=N;i>=1;i--) {
maxl[i-1]=max(maxl[i],maxl[i-1]);
minl[i-1]=min(minl[i],minl[i-1]);
}
//ll xc = 0;
/*for (ll i=1;i<=N;i++) {
//cout << "i="<<i<<", maxl="<<maxl[i]<<", minl="<<minl[i]<<"\n";
if (minl[i]!=INF) {
//ans += abs(xc-minl[i]);
//xc = minl[i];
//ans += abs(xc-maxl[i]);
//xc = maxl[i];
ans += 2*(maxl[i]-minl[i]);
if (i==1) {
if (s<minl[i]) {
ans += 2*(minl[i]-s);
} else if (s>maxl[i]) {
ans += 2*(maxl[i]-s);
}
}
}
}*/
if (minl[1]!=INF) { //below valid if s=0
ans += 2*(maxl[1]-minl[1]);
/*if (s<minl[1]) {
ans += 2*(minl[1]-s);
} else if (s>maxl[1]) {
ans += 2*(s-maxl[1]);
}*/
ans += 2*min(abs(minl[1]-s),abs(maxl[1]-s));
/*ll MD = INF;
for (ll i=0;i<N;i++) {
if (p[i]!=i) {
MD = min(MD,abs(s-i));
}
}
ans += 2*MD;*/
}
//cout << "minl[1],maxl[1]="<<minl[1]<<","<<maxl[1]<<"\n";
//ans += abs(xc);
return ans;
}
/*int main() {
vector<int> p1 = {0,1,4,3,2,5,6};
cout << minimum_walk(p1,3);
}*/
# | 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... |