Submission #429179

#	Time	Username	Problem	Language	Result	Execution time	Memory
429179		albertolg101	Sky Walking (IOI19_walk)	C++17	24 / 100	4057 ms	313036 KiB

walk

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

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

const ll INFLL = 1e18;

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<vector<int>> rmq(h.size(), vector<int> (18));

	for(int i = 0 ; i < h.size() ; i++)
		rmq[i][0] = h[i];

	for(int i = 1 ; (1<<i) < n ; i++)
	{
		for(int j = 0 ; j + (1<<i) - 1 < n ; j++)
		{
			rmq[j][i] = max(rmq[j][i-1], rmq[j+(1<<(i-1))][i-1]);
		}
	};

	function<int(int, int)> query = [&](int l, int r)
	{
		int lg = __lg(r - l + 1);
		return max(rmq[l][lg], rmq[r-(1<<lg)+1][lg]);
	};

	vector<pii> cc;
	vector<vector<int>> d(n);
	d[start].push_back(0);
	d[end].push_back(0);
	cc.push_back({x[start], 0});
	cc.push_back({x[end], 0});

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

		while(l[i] < r[i])
		{
			for(int j = 18 ; j >= 0 ; j--)
			{
				int target = l[i] + (1<<j);

				if(target <= r[i] and query(l[i]+1, target) < y[i])
					l[i] = target;
			}

			l[i]++;
			cc.push_back({x[l[i]], y[i]});
			d[l[i]].push_back(y[i]);
		}

		l[i] = L;
	}

	sort(cc.begin(), cc.end());
	cc.resize(unique(cc.begin(), cc.end()) - cc.begin());

	function<int(int, int)> f = [&](int a, int b)
	{
		return lower_bound(cc.begin(), cc.end(), (pii){a, b}) - cc.begin();
	};

	vector<vector<pair<int, ll>>> g(cc.size());

	for(int i = 0 ; i < m ; i++)
	{
		int last = l[i];

		while(l[i] < r[i])
		{
			for(int j = 18 ; j >= 0 ; j--)
			{
				int target = l[i] + (1<<j);

				if(target <= r[i] and query(l[i]+1, target) < y[i])
					l[i] = target;
			}

			l[i]++;
			int a = f(x[last], y[i]),
				b = f(x[l[i]], y[i]),
				w = x[l[i]] - x[last];

			g[a].push_back({b, w});
			g[b].push_back({a, w});
			last = l[i];
		}
	}

	for(int i = 0 ; i < n ; i++)
	{
		sort(d[i].begin(), d[i].end());

		for(int j = 0 ; j + 1 < d[i].size() ; j++)
		{
			int a = f(x[i], d[i][j]),
				b = f(x[i], d[i][j+1]),
				w = d[i][j+1] - d[i][j];

			g[a].push_back({b, w});
			g[b].push_back({a, w});
		}
	}

	priority_queue<pair<ll, int>> q;
	vector<ll> dp(cc.size(), INFLL);
	vector<bool> flag(cc.size());
	int s = f(x[start], 0);
	dp[s] = 0;
	q.push({0, s});

	while(q.size())
	{
		int nod = q.top().second;
		q.pop();

		if(flag[nod])
			continue;

		flag[nod] = true;

		for(auto i: g[nod])
		{
			if(dp[i.first] > dp[nod] + i.second)
			{
				dp[i.first] = dp[nod] + i.second;
				q.push({-dp[i.first], i.first});
			}
		}
	}

	int e = f(x[end], 0);
	return (dp[e] == INFLL ? -1 : dp[e]);
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0 ; i < h.size() ; i++)
      |                  ~~^~~~~~~~~~
walk.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int j = 0 ; j + 1 < d[i].size() ; j++)
      |                   ~~~~~~^~~~~~~~~~~~~

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