Submission #1213282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213282		guagua0407	Sky Walking (IOI19_walk)	C++20	0 / 100	1198 ms	89960 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 int mxn=2e5+5;
    struct segtree{
        vector<multiset<int>> st;
        segtree(){
            st.resize(mxn*4);
        }
        void update(int pos,ll val,int d,int l=0,int r=mxn-1,int v=1){
            if(d==1) st[v].insert(val);
            else st[v].erase(st[v].find(val));
            if(l==r){
                return;
            }
            int 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(int tl,int tr,int l=0,int r=mxn-1,int 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();
            }
            int 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) {
    int n=(int)x.size();
    int m=(int)l.size();
    vector<int> ys;
    ys.push_back(0);
    for(int i=0;i<n;i++){
        ys.push_back(h[i]);
    }
    for(int i=0;i<m;i++){
        ys.push_back(y[i]);
    }
    sort(all(ys));
    ys.resize(unique(all(ys))-ys.begin());
    vector<vector<int>> st(n),en(n);
    for(int 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,x[n-1],1);
    ll ans;
    for(int i=n-1;i>=0;i--){
        int up=lower_bound(all(ys),h[i])-ys.begin();
        for(auto v:st[i]){
            int pos=lower_bound(all(ys),y[v])-ys.begin();
            dp[v]=inf;
            dp[v]=min(dp[v],st1.query(0,pos)-x[i]+y[v]);
            dp[v]=min(dp[v],st2.query(pos,up)-x[i]-y[v]);
            st1.update(pos,dp[v]+x[i]-y[v],1);
            st2.update(pos,dp[v]+x[i]+y[v],1);
        }
        if(i==0){
            ans=st2.query(0,up)-x[0];
        }
        if(i==n-1) st1.update(0,x[n-1],0);
        for(auto v:en[i]){
            int pos=lower_bound(all(ys),y[v])-ys.begin();
            st1.update(pos,dp[v]+x[r[v]]-y[v],0);
            st2.update(pos,dp[v]+x[r[v]]+y[v],0);
        }
    }
    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