#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=1000007,pot=1<<20;
bool odw[N];
pair<int,int>seg[2*pot+7];
int L,R;
vector<pair<int,int>>V;
void del(int v)
{
v+=pot-1;
seg[v].st=-inf;
while(v>1)
{
seg[v]=max(seg[2*v],seg[2*v+1]);
v/=2;
}
}
pair<int,int>que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg[v];
if(r<a||l>b) return {-inf,0};
return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
void dfs(int v)
{
del(V[v].st+1);
odw[v]=1;
L=min(L,V[v].st);
R=max(R,V[v].nd);
while(true)
{
pair<int,int>p=que(1,V[v].st+1,V[v].nd+1,1,pot);
if(p.st<=V[v].nd) break;
dfs(p.nd);
}
}
vector<pair<int,int>>X;
int W[N];
vector<int>G[N];
int s,n;
ll ans=0;
void dfs1(int v)
{
cout<<v<<endl;
int cL=0,cR=0,S=0;
for(auto u:G[v])
{
if(X[u].st<=s&&X[u].nd>=s)
{
dfs(u);
cL=X[u].st-X[v].st;
cR=X[v].nd-X[u].nd;
}
else if(X[u].nd<s) cL-=X[u].nd-X[u].st;
else cR-=X[u].nd-X[u].st;
S+=X[u].nd-X[u].st;
}
if(v!=1) ans+=2*min(cL,cR);
else ans-=2*S;
}
ll minimum_walk(vector<int>p,int ss)
{
s=ss;
n=sz(p);
for(int i=0;i<n;i++) ans+=abs(i-p[i]);
for(int i=1;i<=2*pot;i++) seg[i].st=-inf;
int c=0;
int A=0,B=n-1;
while(A<s&&p[A]==A) A++;
while(s<B&&p[B]==B) B--;
ans+=2*(B-A);
for(int i=0;i<n;i++)
{
if(odw[i]) continue;
int l=inf,r=-inf,x=i;
while(!odw[x])
{
odw[x]=1;
l=min(l,x);
r=max(r,x);
x=p[x];
}
if(l==r&&(l<A||l>B)) continue;
seg[l+1+pot-1]={r,c};
V.pb({l,r});
c++;
}
for(int i=pot-1;i>0;i--) seg[i]=max(seg[2*i],seg[2*i+1]);
memset(odw,0,sizeof odw);
int it=2;
X.pb({-1,n});
W[n]=1;
for(int i=0;i<c;i++)
{
if(odw[i]) continue;
L=inf,R=-inf;
dfs(i);
X.pb({L,R});
W[R]=it;
it++;
}
vector<int>Q;
for(int i=0;i<=n;i++)
{
if(W[i]==0) continue;
while(sz(Q)>0&&X[Q.back()-1].st>X[W[i]-1].st)
{
//cout<<W[i]<<" "<<Q.back()<<endl;
G[W[i]].pb(Q.back());
Q.pop_back();
}
Q.pb(W[i]);
}
dfs1(1);
return ans;
}
/*
int main()
{
cout<<minimum_walk({0, 2, 3, 1}, 0);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
41172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
41172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
41172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
41172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
41172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
