Submission #138241

#TimeUsernameProblemLanguageResultExecution timeMemory
138241MAMBAAncient Books (IOI17_books)C++17
100 / 100
1680 ms121936 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...