#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42;
int in[nmax],out[nmax];
int tree_in[nmax*4],tree_out[nmax*4];
void update_in(int node)
{
tree_in[node*2]+=tree_in[node];
tree_in[node*2+1]+=tree_in[node];
tree_in[node]=0;
}
void update_in(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)
{
tree_in[node]++;
return;
}
update_in(node);
int av=(l+r)/2;
if(lq<=av)update_in(node*2,l,av,lq,min(av,rq));
if(av<rq)update_in(node*2+1,av+1,r,max(av+1,lq),rq);
}
void go_in(int node,int l,int r)
{
if(l==r)
{
in[l]=tree_in[node];
return;
}
update_in(node);
int av=(l+r)/2;
go_in(node*2,l,av);
go_in(node*2+1,av+1,r);
}
void update_out(int node)
{
tree_out[node*2]+=tree_out[node];
tree_out[node*2+1]+=tree_out[node];
tree_out[node]=0;
}
void update_out(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)
{
tree_out[node]++;
return;
}
update_out(node);
int av=(l+r)/2;
if(lq<=av)update_out(node*2,l,av,lq,min(av,rq));
if(av<rq)update_out(node*2+1,av+1,r,max(av+1,lq),rq);
}
void go_out(int node,int l,int r)
{
if(l==r)
{
out[l]=tree_out[node];
return;
}
update_out(node);
int av=(l+r)/2;
go_out(node*2,l,av);
go_out(node*2+1,av+1,r);
}
long long minimum_walk(vector<int> p, int s)
{
int n=p.size();
while(n-1>s&&p[n-1]==n-1){p.pop_back();n--;}
vector<int> help={};
int where=0;
for(where=0;where<s;where++)
{
if(p[where]!=where)break;
}
for(int i=where;i<n;i++)
help.push_back(p[i]-where);
p=help;
n=p.size();
if(n==0)return 0;
help=p;
sort(help.begin(),help.end());
for(int i=0;i<n;i++)
assert(help[i]==i);
for(int i=0;i<n;i++)
if(i!=p[i])
{
if(i<p[i])
{
update_in(1,1,n,i+1,p[i]);
update_out(1,1,n,i,p[i]-1);
/*
for(int j=i;j<p[i];j++)
out[j]++,in[j+1]++;
*/
}
else
{
update_in(1,1,n,p[i],i-1);
update_out(1,1,n,p[i]+1,i);
/*
for(int j=i;j>p[i];j--)
out[j]++,in[j-1]++;
*/
}
}
go_in(1,0,n-1);
go_out(1,0,n-1);
/*
for(int i=0;i<n;i++)
cout<<in[i]<<" "<<out[i]<<endl;
*/
int maxi=0;
for(int i=0;i<n;i++)
{
maxi=max(maxi,p[i]);
if(i==maxi)
{
if(i!=n-1)
{
in[i]++;
out[i]++;
in[i+1]++;
out[i+1]++;
}
maxi=0;
}
}
for(int i=1;i<n;i++)
{
if(in[i-1]<out[i-1])
{
assert(0==1);
out[i]+=out[i-1]-in[i-1];
in[i-1]=out[i-1];
}
else if(in[i-1]>out[i-1])
{
assert(0==1);
in[i]+=in[i-1]-out[i-1];
out[i-1]=in[i-1];
}
}
assert(in[n-1]==out[n-1]);
long long ans=0;
for(int i=0;i<n;i++)
{
ans=ans+in[i]+out[i];
}
return ans/2;
}
/*
int main()
{
//cout<<minimum_walk({0,2,1,3},2)<<endl;
cout<<minimum_walk({0, 2, 3, 1}, 0)<<endl;
//cout<<minimum_walk({1,0,3,2}, 0)<<endl;
//cout<<minimum_walk({2,3,0,1}, 0)<<endl;
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
916 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
