#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
const int N = 1000 + 10;
int n, m;
vector<int> x, h, l, r, y;
int seg[N << 2];
int Build(int id, int L, int R){
if(L + 1 == R) return seg[id] = h[L];
int mid = (L + R) >> 1;
return seg[id] = max( Build(id << 1, L, mid), Build(id << 1 | 1, mid, R) );
}
int Seg_Get(int id, int l, int r, int L, int R){
if(r <= L || R <= l) return -1;
if(l <= L && R <= r) return seg[id];
int mid = (L + R) >> 1;
return max( Seg_Get(id << 1, l, r, L, mid), Seg_Get(id << 1 | 1, l, r, mid, R) );
}
int Get_Max(int l, int r){ // [l, r]
// cerr << ""
if(r < l) return -1;
return Seg_Get(1, l, r + 1, 0, n);
}
vector<pii> G[N];
void Add_Edge(int a, int b){
// cerr << "!! " << a << ' ' << b << '\n';
int ls = max(l[a], l[b]);
int rs = min(r[a], r[b]);
if(max(y[a], y[b]) <= Get_Max(ls, rs)){
G[a].pb({b, abs(y[a] - y[b])});
G[b].pb({a, abs(y[a] - y[b])});
}
// cerr << "!! " << a << ' ' << b << '\n';
}
vector<int> ins[N], dl[N];
void Add(vector<int> sg){
for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
for(int i : sg){
ins[l[i]].pb(i);
dl[r[i]].pb(i);
}
set< pair<int, int> > st; // y id
for(int i = 0; i < N; i++){
// cerr << "^^ " << i << '\n';
for(auto u : ins[i]){
// cerr << "&& " << u << ' ' << y[u] << '\n';
st.insert({y[u], u});
auto it = st.find({y[u], u});
if(it != st.begin())
Add_Edge(it->S, prev(it) -> S);
if(next(it) != st.end())
Add_Edge(it->S, next(it) -> S);
}
// cerr << "^^ " << i << '\n';
for(auto u : dl[i]){
auto it = st.find({y[u], u});
if(it != st.begin() && next(it) != st.end())
Add_Edge(next(it) -> S, prev(it) -> S);
st.erase(it);
}
}
}
ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
memset(dis, 31, sizeof dis);
dis[src] = 0;
set<pll> st;
st.insert({dis[src], src});
while(!st.empty()){
int fr = st.begin() -> S;
st.erase(st.begin());
for(auto [adj, w] : G[fr]){
assert(w >= 0);
if(dis[adj] > dis[fr] + w){
st.erase({dis[adj], adj});
dis[adj] = dis[fr] + w;
st.insert({dis[adj], adj});
}
}
}
return dis[des];
}
int Get_Last(int l, int r, int yy){
for(int i = r; i >= l; i--)
if(h[i] >= yy)
return i;
return l;
}
int Get_First(int l, int r, int yy){
for(int i = l; i <= r; i++)
if(h[i] >= yy)
return i;
return r;
}
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
if(s > g) swap(s, g);
x = _x;
h = _h;
n = _x.size();
ll ans = x[g] - x[s];
vector<int> lft, mid, rgt;
int u, v;
for(int i = 0; i < (int) _l.size(); i++){
u = _l[i];
v = _r[i];
int a = -1, b = -1, c = -1;
if(u <= s){
a = l.size();
l.pb(u);
r.pb(min(s, v));
y.pb(_y[i]);
}
if(s <= v || u <= g){
b = l.size();
l.pb(max(u, s));
r.pb(min(g, v));
y.pb(_y[i]);
}
if(g <= v){
c = l.size();
l.pb(max(u, g));
r.pb(v);
y.pb(_y[i]);
}
if(a != -1) lft.pb(a);
if(b != -1) mid.pb(b);
if(c != -1) rgt.pb(c);
if(a != -1 && b != -1){
G[a].pb({b, 2 * (x[s] - x[ Get_Last(0, s, _y[i]) ] )});
}
if(b != -1 && c != -1){
G[b].pb({c, 2 * (x[ Get_First(g, n - 1, _y[i]) ] - x[g]) });
}
}
l.pb(s); r.pb(s); y.pb(0);
l.pb(s); r.pb(s); y.pb(0);
l.pb(g); r.pb(g); y.pb(0);
l.pb(g); r.pb(g); y.pb(0);
int src = l.size() - 3;
int des = l.size() - 1;
mid.pb(src - 1);
lft.pb(src);
mid.pb(des - 1);
rgt.pb(des);
m = l.size();
for(int i = 0; i < m; i++)
assert(l[i] <= r[i]);
for(int i = 0; i < m; i++)
assert(0 <= l[i]);
for(int i = 0; i < m; i++)
assert(r[i] <= n);
// l = _l;
// r = _r;
// y = _y;
// for(int i = 0; i < m; i++) mid.pb(i);
Build(1, 0, n);
// debug("A");
Add(lft);
// debug("B");
Add(mid);
// debug("C");
Add(rgt);
// debug("D");
ans += Djik(src, des);
int max_len = 1000000000;
return ans > 1ll * (n + m) * max_len ? -1 : ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Runtime error |
37 ms |
5860 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
3468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
3468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
