This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
int n = (int)X.size(), m = (int)L.size();
vector<vector<pair<int, int>>> todo(n+1);
for(int i = 0; i < m; i++){
todo[L[i]].emplace_back(Y[i], 1);
todo[R[i]+1].emplace_back(Y[i], -1);
}
todo[1].emplace_back(0, -1);
map<int, ll> mp;
mp[0] = 0;
set<int> just_added;
for(int i = 0; i < n; i++){
for(auto [y, op] : todo[i]){
if(op == -1 && !just_added.count(y)) mp.erase(y);
}
just_added.clear();
for(auto [y, op] : todo[i]){
if(op == 1){
auto it = mp.lower_bound(y);
ll v = INF;
if(it != mp.end()) v = min(v, it->second+it->first-y);
if(it != mp.begin()){
it--;
v = min(v, it->second+y-it->first);
}
mp[y] = v;
just_added.insert(y);
}
}
}
if(mp.empty()) return -1;
return mp.begin()->first+mp.begin()->second+X[n-1]-X[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |