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 "books.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
long long minimum_walk(std::vector<int> p, int s)
{
int n=p.size();
ll ans=0;
int start_l=0;
int start_r=n-1;
while(start_l<s && p[start_l]==start_l)
{
start_l++;
}
while(s<start_r && p[start_r]==start_r)
{
start_r--;
}
int mex_low=start_l;
int mex_high=start_r;
vector <bool> v(1000007,0);
int left_limit=start_l;
int right_limit=start_r;
for(int i=start_l;i<=s;i++)
{
ans+=abs(i-p[i]);
v[p[i]]=1;
while(v[mex_low]==1)
{
mex_low++;
}
if(mex_low>i)
{
if(i!=s)
ans+=2;
left_limit=i+1;
}
}
v=vector <bool> (1000007,0);
for(int i=start_r;i>=s;i--)
{
ans+=abs(i-p[i]);
v[p[i]]=1;
while(mex_high>=0 && v[mex_high]==1)
{
mex_high--;
}
if(mex_high<i)
{
if(i!=s)
ans+=2;
right_limit=i-1;
}
}
ans-=abs(s-p[s]);
int lptr=s;
int rptr=s;
v=vector <bool> (1000007,0);
mex_low=s;
mex_high=s;
int mini=p[s];
int maxi=p[s];
v[p[s]]=1;
while(lptr>=left_limit && rptr<=right_limit)
{
while(mini<lptr || rptr<maxi)
{
while(mini<lptr)
{
lptr--;
v[p[lptr]]=1;
mini=min(mini,p[lptr]);
maxi=max(maxi,p[lptr]);
}
while(rptr<maxi)
{
rptr++;
v[p[rptr]]=1;
mini=min(mini,p[rptr]);
maxi=max(maxi,p[rptr]);
}
}
while(mex_low>=0 && v[mex_low]==1)
{
mex_low--;
}
while(v[mex_high]==1)
{
mex_high++;
}
if(lptr==left_limit && rptr==right_limit)
{
break;
}
ans+=2;
mini--;
maxi++;
}
/*if(left_limit>right_limit)
{
ans-=2;
}*/
return ans;
}
# | 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... |