| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1213288 | guagua0407 | Sky Walking (IOI19_walk) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
//#include "walk.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const ll inf=(ll)2e18;
const ll mxn=2e5+5;
struct segtree{
vector<multiset<ll>> st;
segtree(){
st.resize(mxn*4);
}
void update(ll pos,ll val,ll d,ll l=0,ll r=mxn-1,ll v=1){
if(d==1) st[v].insert(val);
else st[v].erase(st[v].find(val));
if(l==r){
return;
}
ll mid=(l+r)/2;
if(pos<=mid) update(pos,val,d,l,mid,v*2);
else update(pos,val,d,mid+1,r,v*2+1);
}
ll query(ll tl,ll tr,ll l=0,ll r=mxn-1,ll v=1){
if(r<tl or tr<l){
return inf;
}
if(tl<=l and r<=tr){
if(st[v].empty()) return inf;
else return *st[v].begin();
}
ll mid=(l+r)/2;
return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
};
}
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) {
ll n=(ll)x.size();
ll m=(ll)l.size();
vector<ll> ys;
ys.push_back(0);
for(ll i=0;i<n;i++){
ys.push_back(h[i]);
}
for(ll i=0;i<m;i++){
ys.push_back(y[i]);
}
sort(all(ys));
ys.resize(unique(all(ys))-ys.begin());
vector<vector<ll>> st(n),en(n);
for(ll i=0;i<m;i++){
st[r[i]].push_back(i);
en[l[i]].push_back(i);
}
segtree st1,st2;
vector<ll> dp(m);
st1.update(0,0,1);
ll ans;
for(ll i=n-1;i>=0;i--){
ll up=lower_bound(all(ys),h[i])-ys.begin();
for(auto v:st[i]){
ll pos=lower_bound(all(ys),y[v])-ys.begin();
dp[v]=inf;
dp[v]=min(dp[v],st1.query(0,pos)+y[v]);
dp[v]=min(dp[v],st2.query(pos,up)-y[v]);
}
for(auto v:st[i]){
st1.update(pos,dp[v]-y[v],1);
st2.update(pos,dp[v]+y[v],1);
}
if(i==0){
ans=st2.query(0,up)+x[n-1]-x[0];
}
if(i==n-1) st1.update(0,0,0);
for(auto v:en[i]){
ll pos=lower_bound(all(ys),y[v])-ys.begin();
st1.update(pos,dp[v]-y[v],0);
st2.update(pos,dp[v]+y[v],0);
}
}
return (ans>=(ll)1e18?-1:ans);
}