#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];
int t[4*maxn];
void build(int v, int tl, int tr)
{
if(tl == tr)
{
t[v] = h[tl];
return;
}
build(v * 2, tl, (tl + tr) / 2);
build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int getup(int v, int tl, int tr, int l, int val)
{
if(t[v] < val || tr < l) return n+1;
if(tl == tr) return tl;
int ret1 = getup(v * 2, tl, (tl + tr) / 2, l, val);
int ret2 = getup(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, val);
if(ret1 != n+1) return ret1;
return ret2;
}
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];
}
build(1, 1, n);
forn(1, i, m)
{
int cur = getup(1, 1, n, l[i], y[i]);
while(cur <= r[i])
{
dot[cur].pb(y[i]);
cur = getup(1, 1, n, cur+1, 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;
}
vector <vector <pair <ll, ll> > > edge;
edge.assign(cnt+10, {});
forn(1, i, n)
{
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;
int cur = getup(1, 1, n, l[i], y[i]);
int se = lower_bound(all(dot[cur]), y[i]) - dot[cur].begin();
se = ver[cur][se];
while(cur <= r[i])
{
if(last != -1)
{
edge[se].pb({last, h[cur]-h[indx]});
edge[last].pb({se, h[cur]-h[indx]});
}
last = se;
indx = cur;
cur = getup(1, 1, n, cur+1, y[i]);
}
}
/* 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 = ver[s][0];
dist[v] = 0;
priority_queue <pair <ll, int> > st;
st.push({0, v});
while(st.size())
{
int v = st.top().s;
if(-st.top().f > dist[v])
{
st.pop();
continue;
}
st.pop();
for(auto to : edge[v])
{
if(dist[to.f] > dist[v] + to.s)
{
dist[to.f] = dist[v]+to.s;
st.push({-dist[to.f], to.f});
}
}
}
if(dist[ver[g][0]] == inf) return -1;
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)
......
82 | FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
| ~~~~~~~~~~~~~~~~
walk.cpp:82:3: note: in expansion of macro 'FOR'
82 | 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)
......
88 | FOR(1, j, dot[i].size())
| ~~~~~~~~~~~~~~~~
walk.cpp:88:3: note: in expansion of macro 'FOR'
88 | FOR(1, j, dot[i].size())
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4033 ms |
10016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4033 ms |
10016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
