이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "books.h"
#define long long long
using namespace std;
const int N = 1e6+5;
long ans = 0;
int n, x, y;
int id[N], L[N], R[N], ptr;
bool chk[N];
void extend(int &l, int &r) {
int ll = min(L[id[l]], L[id[r]]);
int rr = max(R[id[l]], R[id[r]]);
while(ll < l || r < rr) {
if(ll < l) l--;
else r++;
ll = min(ll, min(L[id[l]], L[id[r]]));
rr = max(rr, max(R[id[l]], R[id[r]]));
}
}
long minimum_walk(vector<int> p, int s) {
n = p.size();
x = y = s;
for(int i = 0; i < n; ++i) ans += abs(i - p[i]);
for(int i = 0, ptr = 0; i < n; i++) if(!chk[i]) {
int now = i;
++ptr;
L[ptr] = R[ptr] = i;
while(!chk[now]) {
chk[now] = true, id[now] = ptr;
L[ptr] = min(L[ptr], now);
R[ptr] = max(R[ptr], now);
now = p[now];
}
if(i != p[i]) {
x = min(x, L[ptr]);
y = max(y, R[ptr]);
}
}
int l = s, r = s;
while(x < l || r < y) {
extend(l, r);
int al = l, ar = r;
int bl = l, br = r;
long ca = 0, cb = 0;
while(x < al && ar == r) ca += 2, extend(--al, ar);
while(bl == l && br < y) cb += 2, extend(bl, ++br);
if(ar != r && bl != l) ans += min(ca, cb);
else ans += ca + cb;
l = min(al, bl), r = max(ar, br);
}
return ans;
}
# | 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... |