Submission #1213303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213303		guagua0407	Sky Walking (IOI19_walk)	C++20	0 / 100	564 ms	77372 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=40+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);
    vector<ll> v1(m),v2(m);
    st1.update(0,0,1);
    ll ans;
    set<pair<int,int>> S;
    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]);
            //cout<<v+1<<' '<<pos<<' '<<up<<' '<<dp[v]<<'\n';
        }
        for(auto v:st[i]){
            ll pos=lower_bound(all(ys),y[v])-ys.begin();
            //cout<<"+ "<<pos<<' '<<v<<'\n';
            st1.update(pos,dp[v]-y[v],1);
            st2.update(pos,dp[v]+y[v],1);
            v1[v]=dp[v]-y[v];
            v2[v]=dp[v]+y[v];
            S.insert({y[v],v});
        }
        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();
            //cout<<"- "<<pos<<' '<<v<<'\n';
            st1.update(pos,v1[v],0);
            st2.update(pos,v2[v],0);
            S.erase({y[v],v});
            auto it=S.lower_bound({y[v]+1,0});
            if(S.empty() or it==S.begin()) continue;
            it--;
            int u=(*it).s;
            if(v1[v]+(y[v]-y[u])*2<v1[u]){
                ll pos2=lower_bound(all(ys),y[u])-ys.begin();
                st1.update(pos2,v1[u],0);
                v1[u]=v1[v]+(y[v]-y[u])*2;
                st1.update(pos2,v1[u],1);
            }
            if(v2[v]<v2[u]){
                ll pos2=lower_bound(all(ys),y[u])-ys.begin();
                st2.update(pos2,v2[u],0);
                v2[u]=v2[v];
                st2.update(pos2,v2[u],1);
            }
        }
    }
    return (ans>=(ll)1e18?-1:ans);
}

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