#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 time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
3168 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
3168 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |