#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Seg{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> tree[200200];
int sz;
void init(int n){sz = n;}
void update(int x, ll val, int e){
x += sz;
for (;x;x>>=1) tree[x].emplace(val, e);
}
ll query(int l, int r, int s){
++r;
ll ret = INF;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
while(!tree[l].empty() && tree[l].top().second < s) tree[l].pop();
if (!tree[l].empty()) ret = min(ret, tree[l].top().first);
l++;
}
if (r&1){
--r;
while(!tree[r].empty() && tree[r].top().second < s) tree[r].pop();
if (!tree[r].empty()) ret = min(ret, tree[r].top().first);
}
}
return ret;
}
}tree1, tree2;
struct Line{
int l, r, y, i;
Line(){}
Line(int _l, int _r, int _y, int _i): l(_l), r(_r), y(_y), i(_i) {}
bool operator < (const Line &L) const{
return tie(l, y) < tie(L.l, L.y);
}
}E[100100];
ll D[100100];
ll myabs(ll x){return x<0?-x:x;}
ll dist(ll x1, ll y1, ll x2, ll y2){return myabs(x1-x2) + myabs(y1-y2);}
vector<int> cy;
int getidx(int y){return lower_bound(cy.begin(), cy.end(), y) - cy.begin();}
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) {
int n = x.size(), m = l.size();
if (n==1) return 0;
for (int i=0;i<m;i++) E[i] = Line(x[l[i]], x[r[i]], y[i], i);
sort(E, E+m);
cy = y;
cy.push_back(0);
sort(cy.begin(), cy.end());
cy.erase(unique(cy.begin(), cy.end()), cy.end());
tree1.init(m+1);
tree2.init(m+1);
tree1.update(0, dist(0, 0, 1e9, 1e9), 0);
fill(D, D+m, INF);
//printf("ok\n");
for (int i=0;i<m;){
int j = i;
for (;j<m;j++) if (E[i].l!=E[j].l) break;
for (int k=i;k<j;k++){
D[k] = min(D[k], tree1.query(0, getidx(E[k].y), E[k].l) - dist(E[k].l, E[k].y, 1e9, 1e9));
}
for (int k=j-1;k>=i;k--){
D[k] = min(D[k], tree2.query(getidx(E[k].y)+1, m, E[k].l) - dist(E[k].l, E[k].y, 1e9, 0));
}
for (int k=i;k<j;k++){
tree1.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 1e9), E[k].r);
tree2.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 0), E[k].r);
}
i = j;
}
//for (int i=0;i<m;i++) printf(" %d %d %d -> %lld\n", E[i].l, E[i].r, E[i].y, D[i]);
ll ans = INF;
for (int i=0;i<m;i++) if (E[i].r==x[g]) ans = min(ans, D[i] + dist(E[i].l, E[i].y, x[g], 0));
return ans>=INF/2?-1:ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
39660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
39660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
