#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define cerr if(0) cout
#define cerr2 if(0) cout
int n;
ll minimum_walk(vector<int> p, int s) {
n = size(p);
vector<bool> vis(n, false);
ll cntGroups = -1;
ll ans = 0;
deque<pair<int, int>> regions;
for(ll l = 0, i = 0, r = 0, size = 0, total = 0; r < n; i++) {
if(p[i] != i && !vis[i]) {
ll prev = i;
ll curr = p[i];
while(curr != i) {
vis[prev] = true;
vis[curr] = true;
total += abs(prev - curr);
r = max(r, curr);
prev = p[prev];
curr = p[curr];
}
size += abs(prev - curr);
total += size;
size = 0;
}
vis[i] = true;
if(i == r) {
if(l != r) {
ans += total;
}
regions.push_back({l, r});
l = i+1;
r = i+1;
total = 0;
}
}
while(regions.front().first == regions.front().second && regions.front().second >= s) {
regions.pop_front();
}
while(regions.back().first == regions.back().second && s <= regions.back().first) {
regions.pop_back();
}
return ans + regions.size() + regions.size();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |