#include <bits/stdc++.h>
struct Seg {
int size;
std::vector <int> v;
Seg(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
v.resize(size << 1, -1);
}
inline void build(const std::vector <int>& a) {
build(a, 0, 0, size);
}
void build(const std::vector <int>& a, int now, int l, int r) {
if (!(r - l - 1)) {
if (l < (int) a.size()) {
v[now] = a[l];
}
return;
}
int mid = (l + r) >> 1;
build(a, now * 2 + 1, l, mid);
build(a, now * 2 + 2, mid, r);
v[now] = std::max(v[now + 2 + 1], v[now * 2 + 2]);
}
inline int query(int l, int r) {
return query(l, r, 0, 0, size);
}
int query(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return -1;
}
if (l >= tl && r <= tr) {
return v[now];
}
int mid = (l + r) >> 1;
return std::max(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
}
};
struct Cycle {
std::vector <int> c;
int l, r;
};
long long minimum_walk(std::vector <int> p, int s) {
int n = p.size();
std::vector <bool> vis(n, false);
std::vector <Cycle> cyc;
std::vector <int> part(n, -1);
long long ans = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
vis[i] = true;
int part_now = cyc.size();
cyc.resize(cyc.size() + 1);
cyc.back().c = { i };
cyc.back().l = cyc.back().r = i;
ans += abs(i - p[i]);
int v = p[i];
part[i] = part_now;
while (v != i) {
vis[v] = true;
cyc.back().c.push_back(v);
cyc.back().l = std::min(cyc.back().l, v);
cyc.back().r = std::max(cyc.back().r, v);
part[v] = part_now;
ans += abs(v - p[v]);
v = p[v];
};
}
Seg seg(n);
std::vector <int> bu(n);
for (int i = 0; i < n; i++) {
bu[i] = cyc[part[i]].r;
}
seg.build(bu);
int cmps = 0;
int l = 0, r = 0;
int last;
while (r < n - 1) {
while ((last = seg.query(l, r + 1)) > r) {
r = last;
}
l = ++r;
cmps++;
}
return ans + (cmps - 1) * 2;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '0', found: '4' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '0', found: '4' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '0', found: '4' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '0', found: '4' |
| 10 |
Halted |
0 ms |
0 KB |
- |
