#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
struct walk{
ll l,r,y;
};
vector <walk> all;
const ll MAXN = 1e5 + 100;
const ll INF = 1e18;
vector <pll> g[MAXN*10];
ll dist[MAXN*10];
ll dijkstra(ll s,ll t){
memset(dist,0x3f,sizeof dist);
dist[s] = 0;
priority_queue <pll,vector <pll> ,greater <> > q;
q.push(MP(dist[s],s));
while (!q.empty()){
auto u = q.top().se;
ll val = q.top().fi;
q.pop();
if (dist[u] != val)continue;
for (auto tmp:g[u]){
ll v = tmp.fi,w = tmp.se;
if (dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
q.push(MP(dist[v],v));
}
}
}
if (dist[t] >=INF)dist[t] = -1;
return dist[t];
}
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 S, int G){
ll m = sz(l);
ll n = sz(x);
for (ll i = 0;i < m;i ++){
all.push_back({l[i],r[i],y[i]});
}
sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.y>a2.y;});
vector <ll> order;
order.resize(n);
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](ll x,ll y){return h[x] > h[y];});
// cout<<"OK"<<endl;
vector <pll> vertices;
S=x[S],G=x[G];
vertices.push_back(MP(S,0));
vertices.push_back(MP(G,0));
{
set <ll> s;
s.insert(-1);
s.insert(n);
for (ll i = 0,ptr = 0;i < m;i ++){
while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
s.insert(order[ptr]);
ptr++;
}
vector <ll> tmp;
for (auto it = lower_bound(s.begin(),s.end(),all[i].l);*it <= all[i].r;it ++){
tmp.push_back(x[*it]);
}
for (auto x:tmp)vertices.push_back(MP(x,all[i].y));
}
}
return -1;
sort(vertices.begin(),vertices.end());
// for (auto x:vertices){
// cout<<x.fi<<' '<<x.se<<endl;
// }
auto get_id = [&](pll x){
return lower_bound(vertices.begin(),vertices.end(),x)-vertices.begin();
};
auto add_edge = [&](pll x,pll y){
ll x1 = get_id(x);
ll y1 = get_id(y);
ll w = abs(x.fi-y.fi)+abs(x.se-y.se);
g[x1].push_back(MP(y1,w));
g[y1].push_back(MP(x1,w));
};
{
set <ll> s;
s.insert(-1);
s.insert(n);
for (ll i = 0,ptr = 0;i < m;i ++){
while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
s.insert(order[ptr]);
ptr++;
}
vector <ll> tmp;
for (auto it = lower_bound(s.begin(),s.end(),all[i].l);*it <= all[i].r;it ++){
tmp.push_back(x[*it]);
}
for (ll j = 0;j + 1 < sz(tmp);j ++){
add_edge(MP(tmp[j],all[i].y),MP(tmp[j+1],all[i].y));
}
}
}
for (ll i = 0;i + 1 < sz(vertices);i ++){
if (vertices[i].fi == vertices[i+1].fi)add_edge(vertices[i],vertices[i+1]);
}
return dijkstra(get_id(MP(S,0)),get_id(MP(G,0)));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4096 ms |
30540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4096 ms |
30540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
