#include "walk.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct sky{
int id, l, r, y;
};
bool cmp(sky a, sky b){
if(a.y == b.y)
return a.l < b.l;
return a.y < b.y;
}
vector<int> godown[100009];
vector<int> goup[100009];
vector<ll> dis[100009];
vector<int> add[100009];
vector<int> era[100009];
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
vector<sky> tmp;
for(int i = 0; i < l.size(); ++i)
tmp.pb({i, l[i], r[i], y[i]});
sort(all(tmp), cmp);
vector<sky> top;
for(auto u : tmp){
if(top.size() && top.back().y == u.y && top.back().r == u.l)
top.back().r = u.r;
else
top.pb(u);
}
for(int i = 0; i < top.size(); ++i){
top[i].id = i;
add[x[top[i].l]].pb(i);
era[x[top[i].r]+1].pb(i);
}
set<pii> st;
for(int i = 0; i < x.size(); ++i){
for(auto u : add[i])
st.insert({top[u].y, u});
for(auto u : era[i])
st.erase({top[u].y, u});
for(auto u : st){
if(u.ff > h[i]) break;
godown[u.ss].pb(i);
goup[i].pb(u.ss);
}
/*cout << i << '\n';
for(auto u : goup[i])
cout << top[u].l << ' ' << top[u].r << '\n';*/
sort(all(goup[i]));
dis[i].resize(goup[i].size()+1, 1e18);
}
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
dis[s][0] = 0;
pq.push({0, {s, 0}});
while(pq.size()){
ll d = pq.top().ff;
ll id = pq.top().ss.ff;
ll lev = pq.top().ss.ss;
pq.pop();
if(dis[id][lev] < d)
continue;
for(ll i = 0; i < dis[id].size(); ++i){
ll nd = d;
ll dissurf = 0;
if(lev != 0)
dissurf = top[goup[id][lev-1]].y;
if(i == 0)
nd += dissurf;
else
nd += abs(dissurf-top[goup[id][i-1]].y);
if(nd < dis[id][i]){
dis[id][i] = nd;
pq.push({nd, {id, i}});
}
}
if(lev == 0) continue;
for(auto u : godown[goup[id][lev-1]]){
ll nd = d + abs(x[id]-x[u]);
ll nl = lower_bound(all(goup[u]), goup[id][lev-1])-goup[u].begin()+1;
if(nd < dis[u][nl]){
dis[u][nl] = nd;
pq.push({nd, {u, nl}});
}
}
}
return dis[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:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < l.size(); ++i)
| ~~^~~~~~~~~~
walk.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sky>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < top.size(); ++i){
| ~~^~~~~~~~~~~~
walk.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < x.size(); ++i){
| ~~^~~~~~~~~~
walk.cpp:75:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(ll i = 0; i < dis[id].size(); ++i){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
28780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
28780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
