#include "books.h"
#include <vector>
using namespace std;
#define ll long long
int n;
int p[1000005];
int cycle[1000005];
bool vis[1000005];
int minpos[1000005];
int maxpos[1000005];
int nextcycle = 0;
struct Segtree {
int l, r;
Segtree* lchild;
Segtree* rchild;
pair<int, int> bounds;
};
Segtree* root;
pair<int, int> merge_pair(pair<int, int> p1, pair<int, int> p2)
{
return make_pair(min(p1.first, p2.first), max(p1.second, p2.second));
}
Segtree* build(int l, int r)
{
Segtree* st = new Segtree;
st->l = l; st->r = r;
if (l == r) {
st->lchild = st->rchild = NULL;
st->bounds.first = minpos[l];
st->bounds.second = maxpos[l];
} else {
st->lchild = build(l, (l + r) / 2);
st->rchild = build((l + r) / 2 + 1, r);
st->bounds = merge_pair(st->lchild->bounds, st->rchild->bounds);
}
return st;
}
pair<int, int> query(Segtree* st, int l, int r)
{
if (st->r < l || r < st->l) return make_pair(n, -1);
if (l <= st->l && st->r <= r) return st->bounds;
return merge_pair(query(st->lchild, l, r), query(st->rchild, l, r));
}
pair<int, int> expand(pair<int, int> old)
{
while (true) {
pair<int, int> pair2 = query(root, old.first, old.second);
if (pair2.first == old.first && pair2.second == old.second) return pair2;
old = pair2;
}
}
ll minimum_walk(vector<int> perm, int s) {
n = perm.size();
bool ans0 = true;
for (int i = 0; i < n; i++) {
p[i] = perm[i]; if (p[i] != i) ans0 = false;
}
if (ans0) return 0;
int lbound = 0;
int rbound = n - 1;
while (p[lbound] == lbound) lbound++;
while (p[rbound] == rbound) rbound--;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
minpos[nextcycle] = n;
maxpos[nextcycle] = -1;
int cur = i;
while (!vis[cur]) {
cycle[cur] = nextcycle;
vis[cur] = true;
minpos[nextcycle] = min(minpos[nextcycle], cur);
maxpos[nextcycle] = max(maxpos[nextcycle], cur);
cur = p[cur];
}
nextcycle++;
}
//fprintf(stderr, "HERE");
root = build(0, n - 1);
pair<int, int> cur = expand(make_pair(s, s));
int rounds = 0;
while (cur.first > lbound || cur.second < rbound) {
//fprintf(stderr, "%d %d\n", cur.first, cur.second);
if (cur.first <= lbound) {
cur.second++; cur = expand(cur); rounds++;
} else if (cur.second >= rbound) {
cur.first--; cur = expand(cur); rounds++;
} else {
pair<int, int> left_intv = cur;
int lcount = 0;
while (left_intv.first > lbound && left_intv.second <= cur.second) {
left_intv.first--; left_intv = expand(left_intv); lcount++;
}
pair<int, int> right_intv = cur;
int rcount = 0;
while (right_intv.second < rbound && right_intv.first >= cur.first) {
right_intv.second++; right_intv = expand(right_intv); rcount++;
}
if (lcount < rcount) {
cur = left_intv; rounds += lcount;
} else {
cur = right_intv; rounds += rcount;
}
}
}
ll ans = rounds * 2;
for (int i = 0; i < n; i++) {
ans += (ll)max(p[i] - i, i - p[i]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
300 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
300 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
300 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
300 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '788' |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
300 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
300 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '788' |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
300 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
300 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '788' |
| 23 |
Halted |
0 ms |
0 KB |
- |
