#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*40];
ll dist[MAXN*40];
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];
}
ll SUSSYBAKA;
struct point{
ll x,y,id;
point(ll x1=0,ll y1=0):x(x1),y(y1),id(SUSSYBAKA++){
}
bool operator < (const point &p)const {
return MP(x,y)<MP(p.x,p.y);
}
bool operator == (const point &p)const {
return MP(x,y)==MP(p.x,p.y);
}
};
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 <point> vertices;
vertices.emplace_back(X[S],0);
vertices.emplace_back(X[G],0);
for (auto x:all){
vertices.emplace_back(X[x.l],x.y);
vertices.emplace_back(X[x.r],x.y);
}
auto add_vertex = [&](bool inv){
vector <ll> bd;
for (ll i = inv?n:0;inv?i>=0:i<n;inv?i--:i++){
if (sz(bd) && h[bd.back()] < h[i])bd.pop_back();
bd.push_back(i);
if (i==S||i==G){
ll ptr = sz(bd)-1;
for (auto x:all){
while (ptr>=0&&h[bd[ptr]] < x.y)ptr--;
if (x.l <= ptr && ptr <= x.r){
vertices.emplace_back(X[bd[ptr]],all[i].y);
}
}
}
}
};
add_vertex(0);
add_vertex(1);
vector <pair <pll,bool> > event;
for (auto x:all){
event.emplace_back(MP(X[x.l],x.y),1);
event.emplace_back(MP(X[x.r]+1,x.y),0);
}
sort(event.begin(),event.end());
sort(vertices.begin(),vertices.end());
vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
{
ll ptr = 0;
multiset <ll> ms;
for (auto x:vertices){
while (ptr<sz(event) && event[ptr].fi.fi <= x.x){
if (event[ptr].se)ms.insert(event[ptr].fi.se);
else ms.erase(ms.find((event[ptr].fi.se)));
ptr++;
}
auto tmp = ms.upper_bound(x.y);
if (tmp != ms.end())vertices.emplace_back(x.x,*(tmp));
tmp = ms.lower_bound(x.y);
if (tmp != ms.begin())vertices.emplace_back(x.x,*prev(tmp));
}
}
sort(vertices.begin(),vertices.end());
vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
auto add_edge = [&](point a1,point a2){
ll w = abs(a1.x-a2.x) + abs(a1.y-a2.y);
// cout<<a1.x<<' '<<a1.y<<' '<<a2.x<<' '<<a2.y<<'\n';
g[a1.id].push_back(MP(a2.id,w));
g[a2.id].push_back(MP(a1.id,w));
};
for (ll j = 0;j + 1 < sz(vertices);j ++){
if (vertices[j].x == vertices[j+1].x)add_edge(vertices[j],vertices[j+1]);
}
auto cmp_y = [](point a1,point a2){return MP(a1.y,a1.x) < MP(a2.y,a2.x);};
sort(vertices.begin(),vertices.end(),cmp_y);
auto fi = [&](pll x){
return lower_bound(vertices.begin(),vertices.end(),x,
[](point a1,pll val){return MP(a1.y,a1.x) < MP(val.se,val.fi);})-vertices.begin();
};
vector <ll> cnt(sz(vertices));
for (auto x:all){
cnt[fi(MP(X[x.l],x.y))] ++;
cnt[fi(MP(X[x.r],x.y))] --;
}
for (ll i = 0;i < sz(vertices);i ++){
if (i)cnt[i]+=cnt[i-1];
if (cnt[i]){
add_edge(vertices[i],vertices[i+1]);
}
}
// for (auto x:vertices)cout<<"SUS "<<x.x<<' '<<x.y<<' '<<x.id<<endl;
for (ll i = 0;i < sz(vertices);i ++){
if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[S]),0LL))S = vertices[i].id;
if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[G]),0LL))G = vertices[i].id;
}
return dijkstra(S,G);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
125784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
125776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
139468 KB |
Output is correct |
| 2 |
Runtime error |
176 ms |
225836 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
139468 KB |
Output is correct |
| 2 |
Runtime error |
176 ms |
225836 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
125784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
