#include <bits/stdc++.h>
#include "walk.h"
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
using namespace std;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;
const int N=1e5+1;
struct segtree{
int t[4*N];
void build(int v,int tl,int tr,vec<int> &a){
if(tl==tr){
t[v]=a[tl];
}
else{
int tm=(tl+tr)>>1;
build(2*v,tl,tm,a);build(2*v+1,tm+1,tr,a);
t[v]=max(t[v<<1],t[v<<1|1]);
}
}
int findf(int l,int r,int x,int v,int tl,int tr){
if(tl>r||tr<l||t[v]<x)
return -1;
if(tl==tr)
return tl;
int tm=(tl+tr)>>1;
int j=findf(l,r,x,2*v,tl,tm);
if(j==-1) j=findf(l,r,x,2*v+1,tm+1,tr);
return j;
}
int findl(int l,int r,int x,int v,int tl,int tr){
if(tl>r||tr<l||t[v]<x)
return -1;
if(tl==tr)
return tl;
int tm=(tl+tr)>>1;
int j=findl(l,r,x,2*v+1,tm+1,tr);
if(j==-1) j=findl(l,r,x,2*v,tl,tm);
return j;
}
}sega;
int n;
vec<array<int,3>> process(vec<array<int,3>> arr,int p){
vec<array<int,3>> wi;
for(auto &z : arr){
auto [l,r,h] = z;
int l1=l,r1=r;
l=sega.findf(l,r,h,1,0,n-1);
r=sega.findl(l,r,h,1,0,n-1);
if(l==-1) l=r1+1;
if(r==-1) r=l1-1;
if(l>r) continue;
if(l<=p && r>=p){
int a=sega.findl(l,p,h,1,0,n-1);
int b=sega.findf(p,r,h,1,0,n-1);
assert(a!=-1 && b!=-1);
wi.pb({l,a,h});
wi.pb({a,b,h});
wi.pb({b,r,h});
}
else{
wi.pb({l,r,h});
}
}
return wi;
}
const int NT=2e6+1;
vec<pii> g[2*NT];
map<int,int> cords[N];
set<pii> pos[NT];
int tt=0;
int getid(int i,int j){
// cout<<"I "<<i<<' '<<j<<endl;
if(!cords[i].count(j)){
cords[i][j]=tt++;
pos[j].insert({i,cords[i][j]});
}
return cords[i][j];
}
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 gt){
n=sz(x);
sega.build(1,0,n-1,h);
vec<array<int,3>> arr;
int m=sz(l);
for(int i=0;i<m;i++) arr.pb({l[i],r[i],y[i]});
arr=process(arr,s);
arr=process(arr,gt);
sort(all(arr));
arr.erase(unique(all(arr)),arr.end());
sort(all(arr),[&](array<int,3> f,array<int,3> s){
return f[2]<s[2];
});
//// for(auto &z : arr)
//// cout<<z[0]<<' '<<z[1]<<' '<<z[2]<<endl;
//// exit(0);
m=sz(arr);
vec<vec<int>> adds(n,vec<int>());
vec<vec<int>> dels(n,vec<int>());
for(int i=0;i<m;i++){
adds[arr[i][0]].pb(i);
dels[arr[i][1]].pb(i);
}
set<int> st;
for(int i=0;i<n;i++){
for(auto &z : adds[i]){
auto it=st.lower_bound(z);
getid(i,z);
if(it!=st.begin()){
int c=*prev(it);
getid(i,c);
int v=getid(i,c),u=getid(i,z),w=abs(arr[c][2]-arr[z][2]);
g[v].pb({u,w});
g[u].pb({v,w});
}
}
for(auto &z : adds[i]){
st.insert(z);
}
for(auto &z : dels[i]){
st.erase(z);
}
for(auto &z : dels[i]){
auto it=st.lower_bound(z);
getid(i,z);
if(it!=st.begin()){
int c=*prev(it);
getid(i,c);
}
}
}
int fi=tt++,si=tt++;
for(auto &z : cords[s]){
g[fi].pb({z.s,arr[z.f][2]});
}
for(auto &z : cords[gt]){
// cout<<"SHIS "<<z.s<<' '<<arr[z.f][2]<<endl;
g[z.s].pb({si,arr[z.f][2]});
}
for(int i=0;i<m;i++){
pii last=m_p(-1,-1);
for(auto z : pos[i]){
if(last.f!=-1){
int v=last.s,u=z.s,w=abs(x[z.f]-x[last.f]);
g[v].pb({u,w});
g[u].pb({v,w});
}
last=z;
}
}
for(int i=0;i<n;i++){
pii last=m_p(-1,-1);
for(auto &z : cords[i]){
if(last.f!=-1){
int v=last.s,u=z.s,w=abs(arr[z.f][2]-arr[last.f][2]);
g[v].pb({u,w});
g[u].pb({v,w});
}
last=z;
}
}
const ll inf=1e18;
vec<ll> dst(tt,inf);
priority_queue<pli,vec<pli>,greater<pli>> pq;
dst[fi]=0;
pq.push({dst[fi],fi});
while(!pq.empty()){
auto [d,v]=pq.top();pq.pop();
// cout<<"PQ "<<d<<' '<<v<<endl;
if(dst[v]!=d) continue;
for(auto &z : g[v]){
if(umin(dst[z.f],d+z.s)){
pq.push({dst[z.f],z.f});
}
}
}
if(dst[si]==inf) dst[si]=-1;
return dst[si];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
192972 KB |
Output is correct |
2 |
Correct |
82 ms |
192776 KB |
Output is correct |
3 |
Correct |
85 ms |
192872 KB |
Output is correct |
4 |
Correct |
92 ms |
192860 KB |
Output is correct |
5 |
Correct |
86 ms |
192852 KB |
Output is correct |
6 |
Correct |
86 ms |
192936 KB |
Output is correct |
7 |
Correct |
86 ms |
192852 KB |
Output is correct |
8 |
Correct |
96 ms |
192848 KB |
Output is correct |
9 |
Correct |
85 ms |
192772 KB |
Output is correct |
10 |
Correct |
87 ms |
192856 KB |
Output is correct |
11 |
Correct |
83 ms |
192804 KB |
Output is correct |
12 |
Correct |
84 ms |
192832 KB |
Output is correct |
13 |
Correct |
86 ms |
192880 KB |
Output is correct |
14 |
Correct |
85 ms |
192808 KB |
Output is correct |
15 |
Correct |
84 ms |
192904 KB |
Output is correct |
16 |
Correct |
94 ms |
192844 KB |
Output is correct |
17 |
Correct |
85 ms |
192840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
192860 KB |
Output is correct |
2 |
Correct |
85 ms |
192816 KB |
Output is correct |
3 |
Correct |
583 ms |
254808 KB |
Output is correct |
4 |
Correct |
551 ms |
265708 KB |
Output is correct |
5 |
Correct |
388 ms |
248700 KB |
Output is correct |
6 |
Correct |
406 ms |
248912 KB |
Output is correct |
7 |
Correct |
389 ms |
248796 KB |
Output is correct |
8 |
Correct |
627 ms |
257700 KB |
Output is correct |
9 |
Correct |
532 ms |
259632 KB |
Output is correct |
10 |
Correct |
584 ms |
265704 KB |
Output is correct |
11 |
Correct |
476 ms |
248776 KB |
Output is correct |
12 |
Correct |
398 ms |
243908 KB |
Output is correct |
13 |
Correct |
562 ms |
269928 KB |
Output is correct |
14 |
Correct |
502 ms |
254764 KB |
Output is correct |
15 |
Correct |
490 ms |
257600 KB |
Output is correct |
16 |
Correct |
350 ms |
245064 KB |
Output is correct |
17 |
Correct |
348 ms |
241868 KB |
Output is correct |
18 |
Correct |
976 ms |
285992 KB |
Output is correct |
19 |
Correct |
102 ms |
196600 KB |
Output is correct |
20 |
Correct |
346 ms |
231632 KB |
Output is correct |
21 |
Correct |
349 ms |
240984 KB |
Output is correct |
22 |
Correct |
312 ms |
241872 KB |
Output is correct |
23 |
Correct |
552 ms |
260888 KB |
Output is correct |
24 |
Correct |
341 ms |
242304 KB |
Output is correct |
25 |
Correct |
344 ms |
241864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
219 ms |
213780 KB |
Output is correct |
2 |
Correct |
644 ms |
263668 KB |
Output is correct |
3 |
Correct |
731 ms |
266204 KB |
Output is correct |
4 |
Correct |
776 ms |
276532 KB |
Output is correct |
5 |
Correct |
884 ms |
277520 KB |
Output is correct |
6 |
Correct |
875 ms |
279032 KB |
Output is correct |
7 |
Correct |
398 ms |
239828 KB |
Output is correct |
8 |
Correct |
379 ms |
243748 KB |
Output is correct |
9 |
Correct |
969 ms |
282912 KB |
Output is correct |
10 |
Correct |
398 ms |
247832 KB |
Output is correct |
11 |
Correct |
97 ms |
197232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
219 ms |
213780 KB |
Output is correct |
2 |
Correct |
644 ms |
263668 KB |
Output is correct |
3 |
Correct |
731 ms |
266204 KB |
Output is correct |
4 |
Correct |
776 ms |
276532 KB |
Output is correct |
5 |
Correct |
884 ms |
277520 KB |
Output is correct |
6 |
Correct |
875 ms |
279032 KB |
Output is correct |
7 |
Correct |
398 ms |
239828 KB |
Output is correct |
8 |
Correct |
379 ms |
243748 KB |
Output is correct |
9 |
Correct |
969 ms |
282912 KB |
Output is correct |
10 |
Correct |
398 ms |
247832 KB |
Output is correct |
11 |
Correct |
97 ms |
197232 KB |
Output is correct |
12 |
Correct |
688 ms |
266124 KB |
Output is correct |
13 |
Correct |
639 ms |
275628 KB |
Output is correct |
14 |
Correct |
867 ms |
277380 KB |
Output is correct |
15 |
Correct |
619 ms |
265232 KB |
Output is correct |
16 |
Correct |
606 ms |
265288 KB |
Output is correct |
17 |
Correct |
670 ms |
275132 KB |
Output is correct |
18 |
Correct |
598 ms |
265188 KB |
Output is correct |
19 |
Correct |
589 ms |
265512 KB |
Output is correct |
20 |
Correct |
397 ms |
239568 KB |
Output is correct |
21 |
Correct |
115 ms |
202872 KB |
Output is correct |
22 |
Correct |
465 ms |
259732 KB |
Output is correct |
23 |
Correct |
481 ms |
257816 KB |
Output is correct |
24 |
Correct |
376 ms |
244340 KB |
Output is correct |
25 |
Correct |
406 ms |
253108 KB |
Output is correct |
26 |
Correct |
313 ms |
236404 KB |
Output is correct |
27 |
Correct |
888 ms |
277652 KB |
Output is correct |
28 |
Correct |
583 ms |
275100 KB |
Output is correct |
29 |
Correct |
904 ms |
278672 KB |
Output is correct |
30 |
Correct |
405 ms |
239908 KB |
Output is correct |
31 |
Correct |
926 ms |
282804 KB |
Output is correct |
32 |
Correct |
392 ms |
243548 KB |
Output is correct |
33 |
Correct |
333 ms |
241904 KB |
Output is correct |
34 |
Correct |
439 ms |
250784 KB |
Output is correct |
35 |
Correct |
393 ms |
249208 KB |
Output is correct |
36 |
Correct |
386 ms |
244324 KB |
Output is correct |
37 |
Correct |
345 ms |
240960 KB |
Output is correct |
38 |
Correct |
337 ms |
241884 KB |
Output is correct |
39 |
Correct |
514 ms |
260904 KB |
Output is correct |
40 |
Correct |
345 ms |
242288 KB |
Output is correct |
41 |
Correct |
341 ms |
241864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
192972 KB |
Output is correct |
2 |
Correct |
82 ms |
192776 KB |
Output is correct |
3 |
Correct |
85 ms |
192872 KB |
Output is correct |
4 |
Correct |
92 ms |
192860 KB |
Output is correct |
5 |
Correct |
86 ms |
192852 KB |
Output is correct |
6 |
Correct |
86 ms |
192936 KB |
Output is correct |
7 |
Correct |
86 ms |
192852 KB |
Output is correct |
8 |
Correct |
96 ms |
192848 KB |
Output is correct |
9 |
Correct |
85 ms |
192772 KB |
Output is correct |
10 |
Correct |
87 ms |
192856 KB |
Output is correct |
11 |
Correct |
83 ms |
192804 KB |
Output is correct |
12 |
Correct |
84 ms |
192832 KB |
Output is correct |
13 |
Correct |
86 ms |
192880 KB |
Output is correct |
14 |
Correct |
85 ms |
192808 KB |
Output is correct |
15 |
Correct |
84 ms |
192904 KB |
Output is correct |
16 |
Correct |
94 ms |
192844 KB |
Output is correct |
17 |
Correct |
85 ms |
192840 KB |
Output is correct |
18 |
Correct |
83 ms |
192860 KB |
Output is correct |
19 |
Correct |
85 ms |
192816 KB |
Output is correct |
20 |
Correct |
583 ms |
254808 KB |
Output is correct |
21 |
Correct |
551 ms |
265708 KB |
Output is correct |
22 |
Correct |
388 ms |
248700 KB |
Output is correct |
23 |
Correct |
406 ms |
248912 KB |
Output is correct |
24 |
Correct |
389 ms |
248796 KB |
Output is correct |
25 |
Correct |
627 ms |
257700 KB |
Output is correct |
26 |
Correct |
532 ms |
259632 KB |
Output is correct |
27 |
Correct |
584 ms |
265704 KB |
Output is correct |
28 |
Correct |
476 ms |
248776 KB |
Output is correct |
29 |
Correct |
398 ms |
243908 KB |
Output is correct |
30 |
Correct |
562 ms |
269928 KB |
Output is correct |
31 |
Correct |
502 ms |
254764 KB |
Output is correct |
32 |
Correct |
490 ms |
257600 KB |
Output is correct |
33 |
Correct |
350 ms |
245064 KB |
Output is correct |
34 |
Correct |
348 ms |
241868 KB |
Output is correct |
35 |
Correct |
976 ms |
285992 KB |
Output is correct |
36 |
Correct |
102 ms |
196600 KB |
Output is correct |
37 |
Correct |
346 ms |
231632 KB |
Output is correct |
38 |
Correct |
349 ms |
240984 KB |
Output is correct |
39 |
Correct |
312 ms |
241872 KB |
Output is correct |
40 |
Correct |
552 ms |
260888 KB |
Output is correct |
41 |
Correct |
341 ms |
242304 KB |
Output is correct |
42 |
Correct |
344 ms |
241864 KB |
Output is correct |
43 |
Correct |
219 ms |
213780 KB |
Output is correct |
44 |
Correct |
644 ms |
263668 KB |
Output is correct |
45 |
Correct |
731 ms |
266204 KB |
Output is correct |
46 |
Correct |
776 ms |
276532 KB |
Output is correct |
47 |
Correct |
884 ms |
277520 KB |
Output is correct |
48 |
Correct |
875 ms |
279032 KB |
Output is correct |
49 |
Correct |
398 ms |
239828 KB |
Output is correct |
50 |
Correct |
379 ms |
243748 KB |
Output is correct |
51 |
Correct |
969 ms |
282912 KB |
Output is correct |
52 |
Correct |
398 ms |
247832 KB |
Output is correct |
53 |
Correct |
97 ms |
197232 KB |
Output is correct |
54 |
Correct |
688 ms |
266124 KB |
Output is correct |
55 |
Correct |
639 ms |
275628 KB |
Output is correct |
56 |
Correct |
867 ms |
277380 KB |
Output is correct |
57 |
Correct |
619 ms |
265232 KB |
Output is correct |
58 |
Correct |
606 ms |
265288 KB |
Output is correct |
59 |
Correct |
670 ms |
275132 KB |
Output is correct |
60 |
Correct |
598 ms |
265188 KB |
Output is correct |
61 |
Correct |
589 ms |
265512 KB |
Output is correct |
62 |
Correct |
397 ms |
239568 KB |
Output is correct |
63 |
Correct |
115 ms |
202872 KB |
Output is correct |
64 |
Correct |
465 ms |
259732 KB |
Output is correct |
65 |
Correct |
481 ms |
257816 KB |
Output is correct |
66 |
Correct |
376 ms |
244340 KB |
Output is correct |
67 |
Correct |
406 ms |
253108 KB |
Output is correct |
68 |
Correct |
313 ms |
236404 KB |
Output is correct |
69 |
Correct |
888 ms |
277652 KB |
Output is correct |
70 |
Correct |
583 ms |
275100 KB |
Output is correct |
71 |
Correct |
904 ms |
278672 KB |
Output is correct |
72 |
Correct |
405 ms |
239908 KB |
Output is correct |
73 |
Correct |
926 ms |
282804 KB |
Output is correct |
74 |
Correct |
392 ms |
243548 KB |
Output is correct |
75 |
Correct |
333 ms |
241904 KB |
Output is correct |
76 |
Correct |
439 ms |
250784 KB |
Output is correct |
77 |
Correct |
393 ms |
249208 KB |
Output is correct |
78 |
Correct |
386 ms |
244324 KB |
Output is correct |
79 |
Correct |
345 ms |
240960 KB |
Output is correct |
80 |
Correct |
337 ms |
241884 KB |
Output is correct |
81 |
Correct |
514 ms |
260904 KB |
Output is correct |
82 |
Correct |
345 ms |
242288 KB |
Output is correct |
83 |
Correct |
341 ms |
241864 KB |
Output is correct |
84 |
Correct |
195 ms |
209620 KB |
Output is correct |
85 |
Correct |
807 ms |
272720 KB |
Output is correct |
86 |
Correct |
1415 ms |
321472 KB |
Output is correct |
87 |
Correct |
141 ms |
208240 KB |
Output is correct |
88 |
Correct |
138 ms |
208140 KB |
Output is correct |
89 |
Correct |
143 ms |
208224 KB |
Output is correct |
90 |
Correct |
108 ms |
198764 KB |
Output is correct |
91 |
Correct |
86 ms |
192968 KB |
Output is correct |
92 |
Correct |
105 ms |
196512 KB |
Output is correct |
93 |
Correct |
326 ms |
228844 KB |
Output is correct |
94 |
Correct |
120 ms |
203492 KB |
Output is correct |
95 |
Correct |
480 ms |
262944 KB |
Output is correct |
96 |
Correct |
513 ms |
258920 KB |
Output is correct |
97 |
Correct |
436 ms |
251764 KB |
Output is correct |
98 |
Correct |
421 ms |
253104 KB |
Output is correct |
99 |
Correct |
1959 ms |
370880 KB |
Output is correct |
100 |
Correct |
828 ms |
277064 KB |
Output is correct |
101 |
Correct |
1255 ms |
310200 KB |
Output is correct |
102 |
Correct |
393 ms |
240472 KB |
Output is correct |
103 |
Correct |
405 ms |
243688 KB |
Output is correct |
104 |
Correct |
335 ms |
241748 KB |
Output is correct |
105 |
Correct |
450 ms |
251848 KB |
Output is correct |
106 |
Correct |
439 ms |
252836 KB |
Output is correct |
107 |
Correct |
496 ms |
260228 KB |
Output is correct |
108 |
Correct |
125 ms |
199740 KB |
Output is correct |
109 |
Correct |
678 ms |
262436 KB |
Output is correct |
110 |
Correct |
590 ms |
274668 KB |
Output is correct |
111 |
Correct |
565 ms |
275348 KB |
Output is correct |
112 |
Correct |
401 ms |
249032 KB |
Output is correct |
113 |
Correct |
400 ms |
247484 KB |
Output is correct |