This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
inline bool smin(int &a, int b) { return b < a ? a = b, true : false; }
inline bool smax(int &a, int b) { return a < b ? a = b, true : false; }
const int N = 1e6 + 10;
int A[N], B[N], n;
int A_[N << 1], B_[N << 1];
#define lid i << 1
#define rid lid | 1
inline int getMin(int l, int r) {
int res = l;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) smin(res, B_[l++]);
if (r & 1) smin(res, B_[--r]);
}
return res;
}
inline int getMax(int l, int r) {
int res = r;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) smax(res, A_[l++]);
if (r & 1) smax(res, A_[--r]);
}
return res;
}
inline void build() {
rep(i, 0, n) {
A_[i + n] = A[i];
B_[i + n] = B[i];
}
for (int i = n - 1; i; i--) {
A_[i] = max(A_[lid], A_[rid]);
B_[i] = min(B_[lid], B_[rid]);
}
}
map<pii, pii> mp;
pii extend(int l, int r) {
if (mp.count({l, r})) return mp[{l, r}];
int newL = getMin(l, r);
int newR = getMax(l, r);
if (newL < l || r < newR) return mp[{l, r}] = extend(newL, newR);
return mp[{l, r}] = {l, r};
}
ll minimum_walk(vi p, int s) {
n = p.size();
fill(A, A + n, -1);
fill(B, B + n, n);
ll res = 0;
int l2 = s, r2 = s;
rep(i, 0, n) {
res += abs(i - p[i]);
int a = min(i, p[i]);
int b = i ^ p[i] ^ a;
A[a] = b;
B[b] = a;
if (a != b) {
smin(l2, a);
smax(r2, b);
}
}
build();
int l = s, r = s;
tie(l, r) = extend(l, r);
while (l != l2 && r != r2) {
int l0 = l, r0 = r, l1 = l, r1 = r, aa = 0, bb = 0;
while (true) {
int lp = l0, rp = r0;
tie(l0, r0) = extend(l0 - 1, r0);
aa += 2;
if (rp != r0 || l0 == l2) break;
}
while (true) {
int lp = l1, rp = r1;
tie(l1, r1) = extend(l1, r1 + 1);
bb += 2;
if (lp != l1 || r1 == r2) break;
}
if (r0 == r || l1 == l) {
res += aa + bb;
l = l2, r = r2;
break;
}
res += min(aa, bb);
l = l0, r = r0;
}
while (l != l2) {
res += 2;
tie(l, r) = extend(l - 1, r);
}
while (r != r2) {
res += 2;
tie(l, r) = extend(l, r + 1);
}
return res;
}
Compilation message (stderr)
books.cpp: In function 'll minimum_walk(vi, int)':
books.cpp:91:11: warning: unused variable 'lp' [-Wunused-variable]
int lp = l0, rp = r0;
^~
books.cpp:97:20: warning: unused variable 'rp' [-Wunused-variable]
int lp = l1, rp = r1;
^~
# | 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... |