Submission #427746

#TimeUsernameProblemLanguageResultExecution timeMemory
427746albertolg101Sky Walking (IOI19_walk)C++17
0 / 100
27 ms3168 KiB
#include <bits/stdc++.h> #include "walk.h" using namespace std; using ll = long long; using pii = pair<int, int>; long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> L, std::vector<int> R, std::vector<int> y, int start, int end) { int n = x.size(), m = y.size(); vector<pii> l, r; for(int i = 0 ; i < m ; i++) { l.push_back({L[i], y[i]}); r.push_back({R[i], y[i]}); } sort(l.rbegin(), l.rend()); sort(r.rbegin(), r.rend()); ll ans = -1; multiset<int> s; map<int, ll> dist; dist[0] = 0; s.insert(0); r.push_back({0, 0}); for(int i = 0 ; i < n ; i++) { while(l.size() and l.back().first == i) { ll minDist = 1e18; auto pt = s.lower_bound(l.back().second); if(pt != s.end()) { minDist = *pt - l.back().second + dist[*pt]; } if(pt != s.begin()) { pt = prev(pt); minDist = min(minDist, l.back().second - (*pt) + dist[*pt]); } s.insert(l.back().second); dist[l.back().second] = minDist; l.pop_back(); } while(r.size() and r.back().first == i) { if(i == n - 1) { ll val = x[n-1] - x[0] + dist[r.back().second] + r.back().second; ans = (ans == -1 ? val : min(val, ans)); } s.erase(r.back().second); r.pop_back(); } /* cout << i << ": " ; for(auto i: s) cout << "{" << i << ", " << dist[i] << "} "; cout << endl ; */ if(s.empty()) break; } 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...