#include <bits/stdc++.h>
using namespace std;
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define ll long long
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int maxn=2e5+10;
#define o cout <<"BUG\n";
#define pii pair <int, int>
using namespace std;
const int maxn = 1e5+10;
ll n, m, x[maxn], y[maxn], h[maxn], l[maxn], r[maxn];
vector <ll> dot[maxn], ver[maxn];
vector <pair <ll, ll> > edge[2000100];
long long min_distance(vector<int> X, vector<int> H,
vector<int> L2, vector<int> R2, vector<int> Y2, int s, int g)
{
m = L2.size();
s++, g++;
forn(1, i, m)
{
l[i] = L2[i-1]+1;
r[i] = R2[i-1]+1;
y[i] = Y2[i-1];
}
n = X.size();
forn(1, i, n)
{
x[i] = X[i-1];
h[i] = H[i-1];
}
forn(1, i, m)
{
forn(l[i], j, r[i])
{
if(h[j] >= y[i])
dot[j].pb(y[i]);
}
}
int cnt = 0;
forn(1, i, n)
{
dot[i].pb(0);
sort(all(dot[i]));
dot[i].erase(unique(all(dot[i])), dot[i].end());
ver[i].assign(dot[i].size(), 0);
FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
FOR(1, j, dot[i].size())
{
edge[ver[i][j]].pb({ver[i][j-1], dot[i][j]-dot[i][j-1]});
edge[ver[i][j-1]].pb({ver[i][j], dot[i][j]-dot[i][j-1]});
}
}
forn(1, i, m)
{
int last = -1;
int indx = 0;
forn(l[i], j, r[i])
{
if(h[j] < y[i]) continue;
int se = lower_bound(all(dot[j]), y[i]) - dot[j].begin();
int nw = ver[j][se];
if(last != -1)
{
edge[last].pb({nw, x[j]-x[indx]});
edge[nw].pb({last, x[j]-x[indx]});
}
indx = j;
last = nw;
}
}
/* forn(1, i, n)
{
cout << " FOR " << i << endl;
FOR(0, j, dot[i].size()) cout << dot[i][j] << " " << ver[i][j] << endl;
cout << endl;
}*/
// forn(1, i, cnt)
// for(auto j : edge[i]) cout << i << " " << j.f << " " << j.s << endl;
ll inf = 1e18;
vector <ll> dist(cnt+12);
forn(1, i, cnt)
{
dist[i] = inf;
}
int v = lower_bound(all(dot[s]), 0) - dot[s].begin();
v = ver[s][v];
dist[v] = 0;
set <pair <ll, int> > st;
st.insert({0, v});
while(st.size())
{
int v = st.begin()->s;
st.erase(st.begin());
for(auto to : edge[v])
{
if(dist[to.f] > dist[v] + to.s)
{
st.erase({dist[to.f], to.f});
dist[to.f] = dist[v]+to.s;
st.insert({dist[to.f], to.f});
}
}
}
return dist[ver[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>, int, int)':
walk.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
58 | FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
| ~~~~~~~~~~~~~~~~
walk.cpp:58:3: note: in expansion of macro 'FOR'
58 | FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
| ^~~
walk.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
59 | FOR(1, j, dot[i].size())
| ~~~~~~~~~~~~~~~~
walk.cpp:59:3: note: in expansion of macro 'FOR'
59 | FOR(1, j, dot[i].size())
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
51924 KB |
Output is correct |
| 2 |
Correct |
26 ms |
51944 KB |
Output is correct |
| 3 |
Correct |
22 ms |
51964 KB |
Output is correct |
| 4 |
Incorrect |
22 ms |
51952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
51964 KB |
Output is correct |
| 2 |
Correct |
23 ms |
51972 KB |
Output is correct |
| 3 |
Correct |
814 ms |
142128 KB |
Output is correct |
| 4 |
Correct |
734 ms |
152984 KB |
Output is correct |
| 5 |
Correct |
435 ms |
139408 KB |
Output is correct |
| 6 |
Correct |
1075 ms |
130048 KB |
Output is correct |
| 7 |
Incorrect |
426 ms |
139572 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
63496 KB |
Output is correct |
| 2 |
Runtime error |
508 ms |
444380 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
63496 KB |
Output is correct |
| 2 |
Runtime error |
508 ms |
444380 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
51924 KB |
Output is correct |
| 2 |
Correct |
26 ms |
51944 KB |
Output is correct |
| 3 |
Correct |
22 ms |
51964 KB |
Output is correct |
| 4 |
Incorrect |
22 ms |
51952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
