Submission #427754

#	Time	Username	Problem	Language	Result	Execution time	Memory
427754		albertolg101	Sky Walking (IOI19_walk)	C++17	0 / 100	26 ms	3244 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"

using namespace std; 
using ll = long long;
using pii = pair<int, int>;

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 start, int end) {

	int n = x.size(), 
		m = y.size();

	vector<pii> l, r;

	for(int i = 0 ; i < m ; i++)
	{
		l.push_back({L[i], y[i]});
		r.push_back({R[i], y[i]});
	}

	sort(l.rbegin(), l.rend());
	sort(r.rbegin(), r.rend());

	ll ans = -1;

	multiset<ll> s;
	map<int, ll> dist;

	dist[0] = 0;
	s.insert(0);
	r.push_back({0, 0});

	for(int i = 0 ; i < n ; i++)
	{
		while(l.size() and l.back().first == i)
		{
			ll minDist = 1e18;
			//auto pt = s.lower_bound(l.back().second);
			/*
			if(pt != s.end())
			{
				minDist = *pt - (ll)l.back().second + dist[*pt];
			}

			if(pt != s.begin())
			{
				pt = prev(pt);
				minDist = min(minDist, (ll)l.back().second - (*pt) + dist[*pt]);
			}
			*/

			for(auto i: s)
				minDist = min(minDist, abs(i - (ll)l.back().second) + dist[i]);

			s.insert(l.back().second);
			dist[l.back().second] = minDist;
			l.pop_back();
		}

		while(r.size() and r.back().first == i)
		{
			if(i == n - 1)
			{
				ll val = (ll)(x[n-1] - x[0]) + dist[r.back().second] + (ll)r.back().second;
				ans = (ans == -1 ? val : min(val, ans));
			}

			s.erase(r.back().second);
			r.pop_back();
		}
		/*
		cout << i << ": " ;
		for(auto i: s)
			cout << "{" << i << ", " << dist[i] << "} "; 
		cout << endl ;
		*/
		if(s.empty())
			break;
	}

	return ans;
}

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