이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "books.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 1'000'000;
const int INF = 1e18;
LL minimum_walk(vector<i32> p, i32 s) {
assert(s >= 0);
int n = sz(p);
int ans = 0;
vector<int> cid(n, -1);
vector<pii> range;
For(i, 0, n - 1) if(p[i] != i && cid[i] == -1) {
int cur = i;
int l = n + 1;
int r = -1;
do {
l = min(l, cur);
r = max(r, cur);
ans += abs(p[cur] - cur);
cur = p[cur];
cid[cur] = sz(range);
} while(cur != i);
range.eb(l, r);
}
if(sz(range) == 0) return 0;
int L = 0, R = n - 1;
while(cid[L] == -1) L++;
while(cid[R] == -1) R--;
L = min(L, (int)s);
R = max(R, (int)s);
cerr << L << " " << R << "\n";
vector<int> nxtl(n), nxtr(n);
nxtl[0] = -INF;
For(i, 1, n - 1) {
if(cid[i - 1] != -1) nxtl[i] = i - 1;
else nxtl[i] = nxtl[i - 1];
}
nxtr[n - 1] = INF;
Forr(i, n - 2, 0) {
if(cid[i + 1] != -1) nxtr[i] = i + 1;
else nxtr[i] = nxtr[i + 1];
}
int l = s, r = s;
queue<int> que;
if(cid[s] != -1) que.emplace(cid[s]);
while(l > L && r < R) {
while(sz(que)) {
int id = que.front(); que.pop();
pii rg = range[id];
while(l > rg.F) {
l--;
if(cid[l] != -1) que.emplace(cid[l]);
}
while(r < rg.S) {
r++;
if(cid[r] != -1) que.emplace(cid[r]);
}
}
if(l > L && r < R) {
int l2, r2;
int cl = 0;
l2 = l; r2 = r;
if(l2 == L) cl = INF;
while(r2 == r && l2 != L) {
cl += (l2 - nxtl[l2]) * 2;
l2 = nxtl[l2];
int l3 = range[cid[l2]].F;
int r3 = range[cid[l2]].S;
while(l2 > l3 || r2 < r3) {
if(r2 < r3) {
l2 = l3; r2 = r3;
break;
}
l2--;
if(cid[l2] != -1) {
l3 = min(l3, range[cid[l2]].F);
r3 = max(r3, range[cid[l2]].S);
}
}
}
if(r2 == r) break;
int l8 = l2, r8 = r2;
int cr = 0;
l2 = l; r2 = r;
if(r2 == R) cr = INF;
while(l2 == l && r2 != R) {
cr += (nxtr[r2] - r2) * 2;
r2 = nxtr[r2];
int l3 = range[cid[r2]].F;
int r3 = range[cid[r2]].S;
while(l2 > l3 || r2 < r3) {
if(l2 > l3) {
l2 = l3; r2 = r3;
break;
}
r2++;
if(cid[r2] != -1) {
l3 = min(l3, range[cid[r2]].F);
r3 = max(r3, range[cid[r2]].S);
}
}
}
if(l2 == l) break;
assert(l8 == l2 && r8 == r2);
ans += min(cl, cr);
l = l2; r = r2;
}
}
{
int mx = r;
For(i, r, R) if(cid[i] != -1) {
ans += 2 * max(0ll, i - mx);
mx = max(mx, range[cid[i]].S);
}
}
{
int mn = l;
Forr(i, l, L) if(cid[i] != -1) {
ans += 2 * max(0ll, mn - i);
mn = min(mn, range[cid[i]].F);
}
}
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... |