| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1239155 | vivkostov | 고대 책들 (IOI17_books) | C++20 | 0 ms | 0 KiB |
#pragma once
#include "grader.cpp"
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int l,r;
long long int st;
};
bool cmp(cell a1,cell a2)
{
return a1.l<a2.l;
}
int n,start,br,used[1000005],a[1000005],l[1005][1005],r[1005][1005],ind[1000005],f1,f2;
long long int otg=0,dp[1005][1005];
cell p[1000005];
void dfs(int beg)
{
p[br].l=min(p[br].l,beg);
p[br].r=max(p[br].r,beg);
p[br].st+=abs(a[beg]-beg);
ind[beg]=br;
used[beg]=1;
if(!used[a[beg]])
{
dfs(a[beg]);
}
}
void prec()
{
for(int i=1; i<=n; i++)
{
if(!used[i])
{
br++;
p[br].l=1e9;
dfs(i);
otg+=p[br].st;
}
}
sort(p+1,p+br+1,cmp);
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
f1=i;
break;
}
}
for(int i=n;i>=1;i--)
{
if(a[i]!=i)
{
f2=i;
break;
}
}
/*for(int i=1;i<=br;i++)
{
cout<<p[i].l<<" "<<p[i].r<<" "<<p[i].st<<endl;
}*/
}
void resh()
{
int to=1;
for(int i=1; i<=n; i++)
{
if(p[i].l==p[i].r)continue;
if(to>=p[i].l)
{
to=max(to,p[i].r);
}
else
{
otg+=(p[i].l-to)*2;
to=p[i].r;
}
}
}
void make_dp()
{
l[start][start]=p[ind[start]].l;
r[start][start]=p[ind[start]].r;
for(int i=start;i>0;i--)
{
if(i!=start)
{
l[i][start]=min(l[i+1][start],p[ind[i]].l);
r[i][start]=max(r[i+1][start],p[ind[i]].r);
if(l[i+1][start]<=i)dp[i][start]=dp[i+1][start];
else dp[i][start]=dp[i+1][start]+1;
}
for(int j=start+1;j<=n;j++)
{
l[i][j]=min(l[i][j-1],p[ind[j]].l);
r[i][j]=max(r[i][j-1],p[ind[j]].r);
if(r[i][j-1]>=j)dp[i][j]=dp[i][j-1];
else dp[i][j]=dp[i][j-1]+1;
}
}
otg+=dp[min(f1,start)][max(f2,start)]*2;
}
long long minimum_walk(std::vector<int> p, int s)
{
n=p.size();
for(int i=1; i<=n; i++)
{
a[i]=p[i-1]+1;
}
start=s+1;
prec();
make_dp();
return otg;
}