Submission #1051038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051038		Itamar	Sky Walking (IOI19_walk)	C++14	33 / 100	215 ms	31184 KiB

walk

using namespace std;
#include<vector>
#include<map>
#include<set>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pi pair<ll,ll>
#include<cmath>
#define vi vector<int>
#include<algorithm>
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 = x.size(), m = l.size();
    if(n==1)return 0;
    vector<vi> in(2e5+2);
    vector<vi> out(2e5+2);
    map<ll,ll> dp;
    multiset<ll> se;
    se.insert(1e18+1);
    se.insert(-1e18-1);
    dp[1e18+1]=1e18;
    dp[-1e18-1]=1e18;
    for(int i = 0; i < m;i++){
        dp[y[i]]=1e18;
        in[l[i]].push_back(y[i]);
        out[r[i]].push_back(y[i]);
    }
    out[0].push_back(0);
    dp[0]=0;
    se.insert(0);
    for(int i = 0; i < n; i++){

        for(ll t : in[i])se.insert(t);
        for(ll t : out[i]){
            if(i == n-1){
                dp[0] = min(dp[0], dp[t]+t);
            }
            se.erase(se.find(t));
        }
        for(ll t : out[i]){
            auto it1 = se.lower_bound(t), it2 = se.upper_bound(t);
            it2--;
            dp[*it1] = min(dp[*it1],dp[t]+abs((*it1)-t));
            dp[*it2] = min(dp[*it2],dp[t]+abs((*it2)-t));
        }
        for(ll t : out[i])if(se.find(t) == se.end())dp[t] = 1e18;
    }
    
    if(dp[0] == 1e18)return -1;
    return dp[0]+x[n-1]-x[0];
}

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