Submission #806996

#	Time	Username	Problem	Language	Result	Execution time	Memory
806996		math_rabbit_1028	Sky Walking (IOI19_walk)	C++14	0 / 100	39 ms	13836 KiB

walk

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

int n, m, s, g;
vector<int> x, h, l, r, y;

struct sky {
	int lt, rt, val;
} walk[101010];
bool compare(sky a, sky b) {
	if (a.rt == b.rt) return a.lt > b.lt;
	return a.rt < b.rt;
}
void sort_end() {
	for (int i = 0; i < m; i++) walk[i] = {l[i], r[i], y[i]};
	sort(walk, walk + m, compare);
	for (int i = 0; i < m; i++) {
		l[i] = walk[i].lt;
		r[i] = walk[i].rt;
		y[i] = walk[i].val;
	}
}

vector<int> up, dn;
set< pair<int, int> > pset, mset;
vector<int> add[101010], rem[101010];
void get_updn() {
	for (int i = 0; i < m; i++) add[l[i]].push_back(i);
	for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);

	int p = 0;
	for (int i = 0; i < m; i++) {
		while (p <= r[i]) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				pset.insert({y[tar], tar});
				mset.insert({-y[tar], tar});
			}
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				pset.erase({y[tar], tar});
				mset.erase({-y[tar], tar});
			}
			p++;
		}

		if (pset.lower_bound({y[i] + 1, 0}) == pset.end()) up.push_back(-1);
		else up.push_back(pset.lower_bound({y[i] + 1, 0})->second);
		if (mset.lower_bound({-y[i] + 1, 0}) == mset.end()) dn.push_back(-1);
		else dn.push_back(mset.lower_bound({-y[i] + 1, 0})->second);
	}
}

vector< pair<int, ll> > adj[101010];
void get_edge() {
	for (int i = 0; i < m; i++) {
		adj[i].push_back({up[i], y[up[i]] - y[i]});
		adj[i].push_back({dn[i], y[i] - y[dn[i]]});
	}
	for (int i = 0; i < m; i++) {
		if (l[i] == 0) adj[m].push_back({i, y[i]});
		if (r[i] == n - 1) adj[i].push_back({m + 1, y[i]});
	}
}

ll dis[101010];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
	for (int i = 0; i <= m + 1; i++) dis[i] = 1e18;
	dis[m] = 0;
	pq.push({-dis[m], m});
	while (!pq.empty()) {
		int now = pq.top().second; ll nowdis = -pq.top().first;
		pq.pop();
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i].first;
			if (dis[next] > nowdis + adj[now][i].second) {
				dis[next] = nowdis + adj[now][i].second;
				pq.push({-dis[next], next});
			}
		}
	}
}

ll min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int G) {
	x = X; h = H; l = L; r = R; y = Y; s = S; g = G;
	n = x.size();
	m = l.size();
	sort_end();
	//for (int i = 0; i < m; i++) cout << l[i] << " " << r[i] << " " << y[i] << "\n";
	//cout << "\n";

	get_updn();
	//for (int i = 0; i < m; i++) cout << up[i] << " "; 
	//cout << "\n";
	//for (int i = 0; i < m; i++) cout << dn[i] << " "; 
	//cout << "\n";

	get_edge();

	dijkstra();

	ll ans = dis[m + 1];
	if (ans >= 1e18) return -1;
	ans = ans + x[n - 1] - x[0];
	return ans;
}

Compilation message (stderr)

walk.cpp: In function 'void get_updn()':
walk.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int i = 0; i < adj[now].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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