제출 #388309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388309		LucaDantas	Sky Walking (IOI19_walk)	C++17	0 / 100	27 ms	7252 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;
constexpr int maxn = 1e5+10;

int n, m;

map<long long, long long> mp, qtd;

vector<int> add[maxn], rmv[maxn];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, 
	vector<int> r, vector<int> y, int s, int g) {
	n = (int)h.size(); m = (int)l.size();
	// if(s != 0 || g != n-1) return 0;

	int cnt = 0;
	for(int x : l)
		add[x].push_back(cnt++);
	cnt = 0;
	for(int x : r) {
		if(x != n-1)
			rmv[x].push_back(cnt);
		++cnt;
	}
	mp[0] = 0;
	for(int i = 0; i < n; i++) {
		for(int id : add[i]) {
			++qtd[y[id]];
			if(mp.count(y[id])) continue;
			auto it = mp.lower_bound(y[id]);
			long long here = inf;
			if(it != mp.end()) here = it->second + abs(it->first - y[id]);
			if(it != mp.begin()) {
				--it;
				here = min(here, it->second + abs((it->first) - y[id]));
			}
			mp[y[id]] = here;
		}
		
		for(int id : rmv[i]) if(!(--qtd[y[id]])) mp.erase(y[id]);

		if(!i) mp.erase(0);
		if(!mp.size()) break;
	}
	if(!mp.size()) return -1;

	long long ans = inf;
	for(auto it : mp)
		ans = min(ans, it.second + it.first);
	return ans + x.back();
}

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