Submission #429045

#TimeUsernameProblemLanguageResultExecution timeMemory
429045Dremix10Ancient Books (IOI17_books)C++17
50 / 100
164 ms19736 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define endl '\n' #define F first #define S second #define all(x) (x).begin(),(x).end() const int N = 3e5+1; const ll INF = 2e18; const int MOD = 1e9+7; long long minimum_walk(vector<int> p, int s) { int i,n = p.size(); ll ans = 0; bool ok[n] = {}; int r[n]; int cnt = 0; for(i=0;i<n;i++){ if(p[i] == i){ ok[i] = true; cnt++; } r[i] = -1; } i = 0; while(cnt < n){ while(ok[i]){ i++; //ans++; } int fin = i; ans += abs(p[i] - i); i = p[i]; ok[i] = true; cnt++; while(i != fin){ r[fin] = max(r[fin],i); ans += abs(p[i] - i); i = p[i]; ok[i] = true; cnt++; } //cout<<cnt<<" "<<ans<<" "<<i<<endl; } int border = 0; for(i=0;i<n;i++){ if(r[i] == -1)continue; ans += max(0,i-border)*2; border = max(border,r[i]); } return ans; }
#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...