Submission #592767

#	Time	Username	Problem	Language	Result	Execution time	Memory
592767		Lucpp	Sky Walking (IOI19_walk)	C++17	15 / 100	162 ms	20152 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
	int n = (int)X.size(), m = (int)L.size();
	vector<vector<pair<int, int>>> todo(n+1);
    for(int i = 0; i < m; i++){
        todo[L[i]].emplace_back(Y[i], 1);
        todo[R[i]+1].emplace_back(Y[i], -1);
    }
    todo[1].emplace_back(0, -1);
    map<int, ll> mp;
    mp[0] = 0;
    set<int> just_added;
	for(int i = 0; i < n; i++){
        for(auto [y, op] : todo[i]){
            if(op == -1 && !just_added.count(y)) mp.erase(y);
        }
        just_added.clear();
        for(auto [y, op] : todo[i]){
            if(op == 1){
                auto it = mp.lower_bound(y);
                ll v = INF;
                if(it != mp.end() && it->first <= H[i]) v = min(v, it->second+it->first-y);
                if(it != mp.begin()){
                    it--;
                    v = min(v, it->second+y-it->first);
                }
                if(v == INF) continue;
                mp[y] = v;
                just_added.insert(y);
            }
        }
	}
    if(mp.empty() || mp.begin()->first > H[n-1]) return -1;
    return mp.begin()->first+mp.begin()->second+X[n-1]-X[0];
}

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