Submission #388305

#	Time	Username	Problem	Language	Result	Execution time	Memory
388305		LucaDantas	Sky Walking (IOI19_walk)	C++17	0 / 100	36 ms	3864 KiB

walk

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

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

int n, m;

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

struct Event
{
	int x, t, id;
};

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;

	vector<Event> events;
	int cnt = 0;
	for(int x : l)
		events.push_back({x, 0, cnt++});
	cnt = 0;
	for(int x : r) {
		if(x != n-1)
			events.push_back({x, 1, cnt});
		++cnt;
	}
	sort(events.begin(), events.end(), [](Event a, Event b) {
		if(a.x != b.x) return a.x < b.x;
		return a.t < b.t;
	});
	mp[0] = 0;
	for(int i = 0, ptr = 0; i < n; i++) {
		for(; ptr < 2*m && events[ptr].x == i; ptr++) {
			int id = events[ptr].id;
			if(!events[ptr].t) {
				auto it = mp.lower_bound(y[id]);
				if(it != mp.end()) {
					bool ok = it->first != y[id];
					mp[y[id]] = it->second + abs(it->first - y[id]);
					if(ok) --it;
				}
				if(it != mp.begin()) {
					--it;
					if(!mp.count(y[id])) mp[y[id]] = inf;
					mp[y[id]] = min(mp[y[id]], it->second + abs(it->first - y[id]));
				}
				++qtd[y[id]];
			} else 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