Submission #723919

#TimeUsernameProblemLanguageResultExecution timeMemory
723919GrandTiger1729Sky Walking (IOI19_walk)C++17
0 / 100
190 ms21568 KiB
#include "walk.h" #ifndef EVAL #include "grader.cpp" #endif #include <bits/stdc++.h> using namespace std; const long long INF = 1e18; long long min_distance(vector<int> a, vector<int> h, vector<int> l, vector<int> r, vector<int> b, int s, int g){ int n = a.size(), m = l.size(); vector<vector<int>> ll(n), rr(n); for (int i = 0; i < m; i++){ ll[l[i]].push_back(b[i]); rr[r[i]].push_back(b[i]); } map<int, long long> mp; for (int &j: ll[0]) mp[j] = j; // cerr << "OK" << endl; for (int i = 1; i < n - 1; i++){ set<int> vis; for (int &j: ll[i]){ auto it = mp.lower_bound(j); if (it != mp.end()){ if (it->first != j) mp[j] = it->second + it->first - j; else vis.insert(j); } if (mp.size() && it != mp.begin()){ it--; mp[j] = min(mp[j], it->second + j - it->first); } } // cerr << "OK" << endl; for (int &j: rr[i]){ if (vis.count(j)) continue; auto it = mp.lower_bound(j); { auto it2 = it; it2++; if (it2 != mp.end()) it2->second = min(it2->second, it->second + it2->first - j); } // cerr << "OKK" << endl; if (it != mp.begin()){ auto it2 = it; it2--; it2->second = min(it2->second, it->second + j - it2->first); } mp.erase(it); } // cerr << i << ' ' << mp.size() << endl; // for (auto &it: mp) // cerr << it.first << ' '; // cerr << endl; } long long ans = INF; for (auto &it: mp){ ans = min(ans, it.first + it.second); } ans += a[g] - a[s]; 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...