Submission #1213291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213291		guagua0407	Sky Walking (IOI19_walk)	C++20	15 / 100	2981 ms	349980 KiB

walk

#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=4e5+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]){
            ll pos=lower_bound(all(ys),y[v])-ys.begin();
            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);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43