// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006, MXN = 1003;
int n, st, k, T[N], P[N], A[N], mn[N], mx[N], MC[N];
ll dp[MXN][MXN];
int mark[MXN][MXN];
vector < tuple < int , int , int > > E;
int Find(int v)
{
return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return ;
P[u] = v;
mn[v] = min(mn[v], mn[u]);
mx[v] = max(mx[v], mx[u]);
}
inline void AddEdge(int v, int u, int w)
{
E.push_back({w, v, u});
}
long long minimum_walk(vector < int > _A, int _st)
{
n = (int)_A.size();
st = _st + 1;
for (int i = 1; i <= n; i ++)
A[i] = _A[i - 1] + 1;
ll SM = 0, tot = 0;
for (int i = 1; i <= n; i ++)
SM += abs(A[i] - i);
memset(P, -1, sizeof(P));
for (int i = 1; i <= n; i ++)
mn[i] = mx[i] = i;
set < int > ST;
for (int i = 1; i <= n; i ++)
ST.insert(i);
vector < int > M(n + 1, 0);
vector < pair < int , int > > Roller;
for (int i = 1; i <= n; i ++)
if (!M[i] && A[i] != i)
{
auto Do = [&](int l, int r){
if (l >= r)
return ;
auto it = ST.lower_bound(l);
while (it != ST.end() && * it < r)
Merge(* it, (* it) + 1), it = ST.erase(it);
return ;
};
vector < int > V;
int nw = i;
while (!M[nw])
V.push_back(nw), M[nw] = 1, nw = A[nw];
sort(V.begin(), V.end());
int is = 0;
for (int j : V)
if (j == st)
is = 1;
for (int j = 0; j + 1 < (int)V.size(); j ++)
{
if (V[j + 1] < st || V[j] > st || is)
Do(V[j], V[j + 1]);
else
Roller.push_back({V[j], V[j + 1]});
}
}
/*
for (int i = 1; i <= n; i ++)
if (i != A[i])
{
int l = min(i, A[i]);
int r = max(i, A[i]);
Do(l, min(r, st - 1));
Do(max(st + 1, l), r);
}
*/
vector < pair < pair < int , int > , int > > vec;
for (int i = 1; i <= n; i ++)
if ((Find(i) == i && i != A[i]))
vec.push_back({{mn[i], mx[i]}, i});
if (Find(st) == st && A[st] == st)
{
//T[st] = ++ k;
vec.push_back({{st, st}, st});
}
sort(vec.begin(), vec.end());
for (int i = 0; i < (int)vec.size(); i ++)
T[vec[i].second] = i;
//assert(Find(st) == st);
/*for (int i = 1; i <= n; i ++)
if (i != A[i])
{
int l = min(i, A[i]);
int r = max(i, A[i]);
if (l <= st && st <= r)
AddEdge(T[Find(l)], T[Find(r)], 0);
}*/
memset(MC, -1, sizeof(MC));
for (auto X : Roller)
{
int v = Find(X.first);
int u = Find(X.second);
MC[T[v]] = T[u];
MC[T[u]] = T[v];
//AddEdge(T[v], T[u], 0);
}
/*
for (auto X : vec)
printf("%d , %d :: %d\n", X.first.first, X.first.second, X.second);
for (int i = 0; i < (int)vec.size(); i ++)
printf("%d ", MC[i]);
printf("\n");
*/
if (n <= 1000)
{
memset(dp, 63, sizeof(dp));
int now = -1;
for (int i = 0; i < (int)vec.size(); i ++)
if (vec[i].first.first <= st && vec[i].first.second >= st)
now = i;
assert(now != -1);
dp[now][now] = 0;
mark[now][now] = 1;
int sz = (int)vec.size();
for (int l = now; l >= 0; l --)
for (int r = now; r < sz; r ++)
{
if (!mark[l][r])
continue;
//printf("%d :: %d\n", l, r);
if (l > 0)
{
ll d = dp[l][r] + vec[l].first.first - vec[l - 1].first.second;
int le = l;
int ri = r;
int mn = l - 1;
int mx = r;
while (le > mn || ri < mx)
{
if (le > mn)
{
le --;
if (MC[le] != -1)
mn = min(mn, MC[le]), mx = max(mx, MC[le]);
}
if (ri < mx)
{
ri ++;
if (MC[ri] != -1)
mn = min(mn, MC[ri]), mx = max(mx, MC[ri]);
}
}
dp[le][ri] = min(dp[le][ri], d);
mark[le][ri] = 1;
}
if (r + 1 < sz)
{
ll d = dp[l][r] + vec[l].first.first - vec[l - 1].first.second;
int le = l;
int ri = r;
int mn = l;
int mx = r + 1;
while (le > mn || ri < mx)
{
if (le > mn)
{
le --;
if (MC[le] != -1)
mn = min(mn, MC[le]), mx = max(mx, MC[le]);
}
if (ri < mx)
{
ri ++;
if (MC[ri] != -1)
mn = min(mn, MC[ri]), mx = max(mx, MC[ri]);
}
}
dp[le][ri] = min(dp[le][ri], d);
mark[le][ri] = 1;
}
}
tot = dp[0][sz - 1] * 2;
return SM + tot;
}
assert(0);
for (int i = 0; i + 1 < k; i ++)
AddEdge(vec[i].second, vec[i + 1].second, vec[i + 1].first.first - vec[i].first.second);
sort(E.begin(), E.end());
memset(P, -1, sizeof(P));
int cc = 0;
for (auto X : E)
{
int w, v, u;
tie(w, v, u) = X;
v = Find(v);
u = Find(u);
if (v == u)
continue;
tot += w * 2;
Merge(v, u);
cc ++;
}
assert(cc == k - 1);
tot = tot + SM;
return tot;
/*while (vec.size() > 1 && vec[(int)vec.size() - 2].second >= st)
tot += vec.back().first - vec[(int)vec.size() - 2].second, vec.pop_back();
if (vec.size() && vec.back().first >= st)
tot += vec.back().first - st, vec.pop_back();
reverse(vec.begin(), vec.end());
while (vec.size() > 1 && vec[(int)vec.size() - 2].first <= st)
tot += vec[(int)vec.size() - 2].first - vec.back().second, vec.pop_back();
if (vec.size() && vec.back().second <= st)
tot += st - vec.back().second, vec.pop_back();
if (vec.size())
{
assert(vec.size() == 1 && vec[0].first <= st && st <= vec[0].second);
if (A[st] == st)
{
int l = st;
while (l && A[l] == l)
l --;
assert(l >= vec[0].first);
int Best = st - l;
int r = st;
while (r <= n && A[r] == r)
r ++;
assert(r <= vec[0].second);
Best = min(Best, r - st);
tot += Best;
}
}
tot = tot * 2 + SM;
return tot;*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
3rd lines differ - on the 1st token, expected: '6', found: '-60' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
3rd lines differ - on the 1st token, expected: '6', found: '-60' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
3rd lines differ - on the 1st token, expected: '6', found: '-60' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16384 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3076' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16000 KB |
3rd lines differ - on the 1st token, expected: '6', found: '-60' |
| 2 |
Halted |
0 ms |
0 KB |
- |
