#include "books.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define fi first
#define se second
using ll = long long;
struct segment_tree {
#define il i * 2
#define ir i * 2 + 1
vector <int> val;
int n, x, y, res;
void build(int i, int l, int r,
const vector <int> &idx) {
if (l == r) val[i] = idx[l];
else {
int m = (l + r) / 2;
build(il, l, m, idx);
build(ir, m + 1, r, idx);
val[i] = max(val[il], val[ir]);
}
}
void init(const vector <int> &idx) {
n = idx.size();
val.resize(n * 4);
build(1, 0, n - 1, idx);
}
void rep(int i, int l, int r, int v) {
if (l == r) val[i] = v;
else {
int m = (l + r) / 2;
if (m >= x) rep(il, l, m, v);
else rep(ir, m + 1, r, v);
val[i] = max(val[il], val[ir]);
}
}
void get(int i, int l, int r) {
if (l >= x && r <= y) {
res = max(res, val[i]);
return;
}
int m = (l + r) / 2;
if (m >= x) get(il, l, m);
if (m < y) get(ir, m + 1, r);
}
void rep(int p, int v) {
x = p; rep(1, 0, n - 1, v);
}
int get(int l, int r) {
x = l; y = r; res = -1;
get(1, 0, n - 1); return res;
}
};
vector <int> lef, rig, ord;
vector <vector <int>> own;
segment_tree seg;
vector <char> vis;
void dfs(int u) {
vis[u] = 1;
for (int i : own[u]) seg.rep(i, -1);
int v = seg.get(lef[u], rig[u]);
while (v >= 0) {
dfs(v);
v = seg.get(lef[u], rig[u]);
}
ord.push_back(u);
}
}
ll minimum_walk(vector<int> p, int s) {
int cnt = 0, n = p.size();
vector <int> idx(n, -1);
for (int i = 0; i < n; i++) {
if (~idx[i]) continue;
int u = i;
lef.push_back(i);
rig.push_back(i);
own.emplace_back();
while (idx[u] < 0) {
own[cnt].push_back(u);
lef[cnt] = min(lef[cnt], u);
rig[cnt] = max(rig[cnt], u);
idx[u] = cnt; u = p[u];
}
cnt++;
}
vis.assign(n, 0); seg.init(idx);
for (int u = 0; u < cnt; u++)
if (!vis[u]) dfs(u);
reverse(ord.begin(), ord.end());
vis.assign(n, 0); seg.init(idx);
vector <pair <int, int>> tmp;
int mi = s, ma = s;
for (int u : ord)
if (!vis[u]) {
dfs(u); int l = -1, r = n;
for (int i : own[u]) {
if (i < s) l = max(l, i);
if (i > s) r = min(r, i);
}
if (l >= 0 && r < n)
seg.rep(r, r);
else if (l >= 0)
mi = min(mi, l);
else if (r < n)
ma = max(ma, r);
}
sort(tmp.rbegin(), tmp.rend());
long long res = 2ll *
(max(ma, seg.val[1]) - mi);
for (auto &p : tmp) {
seg.rep(p.se, -1);
res = min(res, 2ll * (max
(ma, seg.val[1]) - min(mi, p.fi)));
swap(p.fi, p.se);
}
for (int i = 0; i < n; i++)
res += abs(i - p[i]);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
292 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3888' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
