This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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;
using namespace __gnu_pbds;
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];
gp_hash_table<int,int> cordt[N];
vec<pii> cords[N];
vec<pii> pos[NT];
int tt=0;
int getid(int i,int j){
// cout<<"I "<<i<<' '<<j<<endl;
if(cordt[i].find(j)==cordt[i].end()){
cordt[i][j]=tt++;
pos[j].pb({i,cordt[i][j]});
}
return cordt[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);
}
}
}
for(int i=0;i<n;i++){
for(auto &z : cordt[i])
cords[i].pb(z);
cordt[i].clear();
sort(all(cords[i]));
}
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]);
assert(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];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |