Submission #135999

#TimeUsernameProblemLanguageResultExecution timeMemory
135999rondojimAncient Books (IOI17_books)C++17
50 / 100
216 ms35992 KiB
#include <bits/stdc++.h> #include "books.h" #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; const int maxN = 1e6 + 10; bool mark[maxN]; vector <pii> que; long long minimum_walk(std::vector<int> p, int s) { int n = p.size(), m = 0; ll ans = 0; for (int i=0; i<n; i++) { if(mark[i]) continue ; int curr = i, mn = n, sz = 0, mx = 0; while(!mark[curr]) { mn = min(mn, curr); mx = max(mx, curr); sz ++; mark[curr] = true; ans += abs(p[curr] - curr); curr = p[curr]; } que.pb({mn, mx}); } sort(que.begin(), que.end()); int len = que.size(); int maxR = 0, currL = 0; vector <pii> res; for (int i=0; i<len; i++) { if(maxR >= que[i].F) maxR = max(maxR, que[i].S); else { res.pb({currL, maxR}); currL = maxR + 1; maxR = que[i].S; } } res.pb({currL, maxR}); for (int i=0; i<(int)res.size(); i++) if(res[i].F != res[i].S) m = i; return ans + 2LL * m; }
#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...