#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(x[0], 0, 1e9, 1e9), x[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 |
7 ms |
12756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
39796 KB |
Output is correct |
2 |
Correct |
558 ms |
72744 KB |
Output is correct |
3 |
Correct |
647 ms |
74140 KB |
Output is correct |
4 |
Correct |
619 ms |
76796 KB |
Output is correct |
5 |
Correct |
541 ms |
89196 KB |
Output is correct |
6 |
Correct |
648 ms |
84328 KB |
Output is correct |
7 |
Correct |
331 ms |
45344 KB |
Output is correct |
8 |
Correct |
520 ms |
67968 KB |
Output is correct |
9 |
Correct |
563 ms |
86900 KB |
Output is correct |
10 |
Correct |
202 ms |
85444 KB |
Output is correct |
11 |
Correct |
23 ms |
14416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
39796 KB |
Output is correct |
2 |
Correct |
558 ms |
72744 KB |
Output is correct |
3 |
Correct |
647 ms |
74140 KB |
Output is correct |
4 |
Correct |
619 ms |
76796 KB |
Output is correct |
5 |
Correct |
541 ms |
89196 KB |
Output is correct |
6 |
Correct |
648 ms |
84328 KB |
Output is correct |
7 |
Correct |
331 ms |
45344 KB |
Output is correct |
8 |
Correct |
520 ms |
67968 KB |
Output is correct |
9 |
Correct |
563 ms |
86900 KB |
Output is correct |
10 |
Correct |
202 ms |
85444 KB |
Output is correct |
11 |
Correct |
23 ms |
14416 KB |
Output is correct |
12 |
Correct |
569 ms |
73520 KB |
Output is correct |
13 |
Correct |
539 ms |
77928 KB |
Output is correct |
14 |
Correct |
475 ms |
90792 KB |
Output is correct |
15 |
Correct |
345 ms |
95720 KB |
Output is correct |
16 |
Correct |
376 ms |
72748 KB |
Output is correct |
17 |
Correct |
354 ms |
78264 KB |
Output is correct |
18 |
Correct |
330 ms |
95704 KB |
Output is correct |
19 |
Correct |
368 ms |
70920 KB |
Output is correct |
20 |
Correct |
277 ms |
45240 KB |
Output is correct |
21 |
Correct |
29 ms |
16824 KB |
Output is correct |
22 |
Correct |
368 ms |
62216 KB |
Output is correct |
23 |
Correct |
435 ms |
66956 KB |
Output is correct |
24 |
Correct |
373 ms |
73696 KB |
Output is correct |
25 |
Correct |
364 ms |
59572 KB |
Output is correct |
26 |
Correct |
371 ms |
72756 KB |
Output is correct |
27 |
Correct |
472 ms |
88500 KB |
Output is correct |
28 |
Correct |
499 ms |
71036 KB |
Output is correct |
29 |
Correct |
564 ms |
85040 KB |
Output is correct |
30 |
Correct |
256 ms |
45296 KB |
Output is correct |
31 |
Correct |
492 ms |
86736 KB |
Output is correct |
32 |
Correct |
171 ms |
82016 KB |
Output is correct |
33 |
Correct |
174 ms |
89600 KB |
Output is correct |
34 |
Correct |
215 ms |
79640 KB |
Output is correct |
35 |
Correct |
273 ms |
74768 KB |
Output is correct |
36 |
Correct |
189 ms |
69760 KB |
Output is correct |
37 |
Correct |
121 ms |
74668 KB |
Output is correct |
38 |
Correct |
125 ms |
75440 KB |
Output is correct |
39 |
Correct |
241 ms |
79760 KB |
Output is correct |
40 |
Correct |
154 ms |
79124 KB |
Output is correct |
41 |
Correct |
131 ms |
73248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
12756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |