Submission #590356

#	Time	Username	Problem	Language	Result	Execution time	Memory
590356		Soumya1	Sky Walking (IOI19_walk)	C++17	0 / 100	173 ms	36140 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = y.size();
	multiset<pair<int, long long>> st;
	vector<int> add[n], rem[n];
	for (int i = 0; i < m; i++) {
		add[l[i]].push_back(i);
		rem[r[i]].push_back(i);
	}
	vector<long long> ans(m);
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> nw;
		for (int j : add[i]) {
			if (i == 0) nw.push_back({y[j], y[j]}), ans[j] = y[j];
			else {
				long long v = 1e18;
				auto up = st.upper_bound({y[j], -5});
				if (up != st.end()) v = min(v, (*up).first - y[j] + (*up).second); 
				auto down = st.lower_bound({y[j], -5});
				if (!st.empty() && up == down && down != st.begin()) {
					down--;
				  v = min(v, y[j] - (*down).first + (*down).second); 
				}
				ans[j] = v;
				nw.push_back({y[j], ans[j]});
			}
		}
		for (auto x : nw) st.insert(x);
		for (int j : rem[i]) st.erase(st.find({y[j], ans[j]}));
	}
	long long ret = 1e18;
	for (int i = 0; i < m; i++) {
		if (r[i] == n - 1) ret = min(ret, ans[i] + y[i] + x[n - 1] - x[0]);
	} 
	if (ret == 1e18) ret = -1;
	return ret;
}

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