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;
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;
for (ll i=0;i<N;i++) {
pf[i+1]=pf[i]+flux[i];
//cout << "x="<<(i+1)<<", pf[x]="<<pf[i+1]<<"\n";
}
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;
ll ans = 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);
}
}
}
}
//ans += abs(xc);
return ans;
}
/*int main() {
vector<int> p1 = {0,2,3,1};
cout << minimum_walk(p1,0);
}*/
# | 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... |