Submission #427465

#TimeUsernameProblemLanguageResultExecution timeMemory
427465TangentAncient Books (IOI17_books)C++17
50 / 100
225 ms23504 KiB
#include "books.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vii; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vii> vvii; typedef vector<vll> vvll; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; #define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++) #define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--) #define rep(i, n) ffor(i, 0, n) #define forin(x, a) for (auto &x: a) #define all(a) a.begin(), a.end() long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); vii seen(n); vpii segs; ll res = 0; rep(i, n) { if (!seen[i]) { seen[i] = true; int lo = i, hi = i; res += abs(p[i] - i); int curr = p[i]; while (curr != i) { lo = min(lo, curr); hi = max(hi, curr); seen[curr] = true; res += abs(curr - p[curr]); curr = p[curr]; } if (lo != hi) segs.emplace_back(lo, hi + 1); } } sort(all(segs)); reverse(all(segs)); if (segs.empty()) return res; vpii merged = {segs.back()}; segs.pop_back(); while (!segs.empty()) { if (segs.back().first < merged.back().second) { merged.back().second = max(merged.back().second, segs.back().second); } else { merged.emplace_back(segs.back()); } segs.pop_back(); } int curr = 0; forin(seg, merged) { res += 2 * (seg.first - curr); curr = seg.second - 1; } return res; }
#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...