// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, st, k, T[N], P[N], A[N], mn[N], mx[N];
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());
for (int j = 0; j + 1 < (int)V.size(); j ++)
{
if (V[j + 1] < st || V[j] > st)
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]) || i == st)
T[i] = ++ k, vec.push_back({{mn[i], mx[i]}, T[i]});
sort(vec.begin(), vec.end());
//for (auto X : vec)
// printf("%d , %d :: %d\n", X.first.first, X.first.second, X.second);
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);
}*/
for (auto X : Roller)
{
int v = Find(X.first);
int u = Find(X.second);
AddEdge(T[v], T[u], 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 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4224 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4224 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4224 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4352 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '4032' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4224 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
