#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define int int64_t
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
constexpr static int INF = 1e17;
vector<array<int,3>> is[MXN];// Height, prev, next
vector<bool> visited[MXN];
vector<int> min_dist[MXN];
void search_insert(int i, int j, int ch, priority_queue<array<int, 3>>& pq, vector<int32_t>& x)
{
auto it = lower_bound(is[j].begin(), is[j].end(), array<int, 3>({is[i][ch][0], -1, -1}));
assert(it != is[j].end() && (*it)[0] == is[i][ch][0]);
int nh = it - is[j].begin();
if (min_dist[j][nh] > min_dist[i][ch] + abs(x[j] - x[i]))
{
min_dist[j][nh] = min_dist[i][ch] + abs(x[j] - x[i]);
pq.push({-min_dist[j][nh], j, nh});
}
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g)
{
for (int i = 0; i < l.size(); i++)
{
int prev = -1;
for (int j = l[i]; j <= r[i]; j++)
{
if (h[j] >= y[i])
{
is[j].pb({y[i], prev, -1});
if (prev != -1)
is[prev].back()[2] = j;
prev = j;
}
}
}
is[s].pb({0, -1, -1});
is[g].pb({0, -1, -1});
for (int i = 0; i < x.size(); i++)
{
sort(is[i].begin(), is[i].end());
min_dist[i] = vector<int>(is[i].size(), INF);
visited[i] = vector<bool>(is[i].size(), false);
}
priority_queue<array<int, 3>> pq;
pq.push({0, s, 0});
min_dist[s][0] = 0;
while (pq.size())
{
auto [dist, i, ch] = pq.top();
pq.pop();
if (visited[i][ch])
continue;
visited[i][ch] = true;
debug(i, ch, min_dist[i][ch]);
if (i == 0 && ch == 0)
debug(is[0][0]);
if (is[i][ch][1] != -1)
search_insert(i, is[i][ch][1], ch, pq, x);
if (is[i][ch][2] != -1)
search_insert(i, is[i][ch][2], ch, pq, x);
if (ch > 0 && min_dist[i][ch] + is[i][ch][0] - is[i][ch-1][0] < min_dist[i][ch-1])
{
min_dist[i][ch-1] = min_dist[i][ch] + is[i][ch][0] - is[i][ch-1][0];
pq.push({-min_dist[i][ch-1], i, ch-1});
}
if (ch < is[i].size()-1 && min_dist[i][ch] + is[i][ch+1][0] - is[i][ch-1][0] < min_dist[i][ch+1])
{
min_dist[i][ch+1] = min_dist[i][ch] - is[i][ch][0] + is[i][ch+1][0];
pq.push({-min_dist[i][ch+1], i, ch+1});
}
for (int j = ch+1; j < is[i].size(); j++)
{
if (min_dist[i][ch] + is[i][j][0] - is[i][ch][0] >= min_dist[i][j])
break;
min_dist[i][j] = min_dist[i][ch] - is[i][ch][0] + is[i][j][0];
pq.push({-min_dist[i][j], i, j});
}
}
return min_dist[g][0];
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < l.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < x.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:79:10: warning: comparison of integer expressions of different signedness: 'std::tuple_element<2, std::array<long int, 3> >::type' {aka 'long int'} and 'std::vector<std::array<long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (ch < is[i].size()-1 && min_dist[i][ch] + is[i][ch+1][0] - is[i][ch-1][0] < min_dist[i][ch+1])
| ~~~^~~~~~~~~~~~~~~~
walk.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int j = ch+1; j < is[i].size(); j++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8812 KB |
Output is correct |
| 3 |
Correct |
281 ms |
43012 KB |
Output is correct |
| 4 |
Incorrect |
262 ms |
45352 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
15444 KB |
Output is correct |
| 2 |
Runtime error |
694 ms |
412316 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
15444 KB |
Output is correct |
| 2 |
Runtime error |
694 ms |
412316 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
