Submission #122970

#TimeUsernameProblemLanguageResultExecution timeMemory
122970someone_aaAncient Books (IOI17_books)C++17
50 / 100
845 ms31600 KiB
#include "books.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 1000100; bool suffix[maxn]; int n, loc[maxn]; long long minimum_walk(std::vector<int> p, int s) { n = p.size(); suffix[n] = true; for(int i=n-1;i>=0;i--) { suffix[i] = suffix[i+1] && (p[i] == i); loc[p[i]] = i; } ll result = 0LL; set<int>need; for(int i=0;i<n;i++) { if(suffix[i+1]) break; // if p[i] is in need if(need.find(p[i]) != need.end()) need.erase(p[i]); if(loc[i] > i) need.insert(i); /*cout<<"i: \n"; for(int i:need) { cout<<i<<" "; } cout<<"\n";*/ result += 2LL * max(1, int(need.size())); } return result; }
#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...