Submission #1242729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242729		Boas	Sky Walking (IOI19_walk)	C++20	15 / 100	116 ms	18488 KiB

walk

#include "walk.h"

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

#define int long long

#define loop(n, i) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()

typedef pair<int, int> ii;
typedef vector<int32_t> vi32;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef vector<vi32> vvi32;

i64 INF = 1e18;

i64 min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g)
{
	int n = sz(x), m = sz(l);
	vvi32 endsHere(n), startHere(n);
	loop(m, i) endsHere[r[i]].pb(i);
	loop(m, i) startHere[l[i]].pb(i);
	vi64 dis(m, INF);
	sii active; // {y, ix}
	i64 res = INF;
	for (int p = 0; p < n; p++)
	{
		for (int i : startHere[p])
		{
			int y2 = y[i];
			auto nxt = active.lower_bound({y2, 0});
			if (nxt != active.end())
			{
				auto [y1, j] = *nxt;
				if (y1 <= h[p])
					dis[i] = min(dis[i], dis[j] + abs(y1 - y2));
			}
			if (nxt != begin(active))
			{
				auto [y1, j] = *--nxt;
				dis[i] = min(dis[i], dis[j] + abs(y1 - y2));
			}
		}
		for (int i : startHere[p])
		{
			active.insert({y[i], i});
			if (p == 0)
				dis[i] = y[i];
		}
		if (p == g)
		{
			for (auto [y1, i] : active)
			{
				res = min(res, dis[i] + y1);
			}
		}
		for (int i : endsHere[p])
		{
			active.erase({y[i], i});
		}
	}
	if (res == INF)
		return -1;
	return res + x[g] - x[s];
}

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