Submission #285980

#	Time	Username	Problem	Language	Result	Execution time	Memory
285980		cookiedoth	Sky Walking (IOI19_walk)	C++14	33 / 100	305 ms	25192 KiB

walk

#include "walk.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <deque>
#include <queue>
#include <algorithm>
#include <string>
#include <cassert>
#include <memory>
#include <numeric>
#include <functional>
#include <random>
#define ll long long
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define length(a) ((int)a.size())

using namespace std;

template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(const T &x, ostream &out = cerr) {
	output(all(x), out);
}

template<class T> int chkmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmax(T &a, const T &b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

struct bridge {
	int l, r;
	ll y;
};

const ll INF = 1e18;
int n, m;
vector<ll> x, h;
vector<bridge> E;
map<ll, ll> mp;
vector<vector<pair<int, ll> > > events;

ll solve(int s, int g) {
	events.resize(n);
	for (int i = 0; i < E.size(); ++i) {
		events[E[i].l].emplace_back(0, E[i].y);
		events[E[i].r].emplace_back(1, E[i].y);
	}
	ll ans = INF;
	set<int> new_chel;
	int it = 0;
	for (int i = 0; i < n; ++i) {
		sort(all(events[i]));
		new_chel.clear();
		for (auto pp : events[i]) {
			it++;
			ll y = pp.second;
			if (pp.first == 0) {
				// cerr << "insert " << y << endl;
				new_chel.insert(y);
				auto it = mp.lower_bound(y);
				ll val = INF;
				if (i == 0) {
					val = y;
				}
				if (it != mp.end()) {
					chkmin(val, it->second + it->first - y);
				}
				if (it != mp.begin()) {
					it--;
					chkmin(val, it->second + y - it->first);
				}
				mp[y] = val;
				// cerr << "dp = " << val << endl;
			} else {
				if (new_chel.find(y) != new_chel.end()) {
					continue;
				}
				// cerr << "erase " << y << endl;
				auto it = mp.find(y);
				assert(it != mp.end());
				if (next(it) != mp.end()) {
					ll y1 = next(it)->first;
					chkmin(mp[y1], mp[y] + y1 - y);
				}
				if (it != mp.begin()) {
					ll y1 = prev(it)->first;
					chkmin(mp[y1], mp[y] + y - y1);
				}
				if (i == n - 1) {
					chkmin(ans, it->first + it->second + x[n - 1] - x[0]);
				}
				mp.erase(it);
			}
		}
		// cerr << "i = " << i << endl;
		// for (auto pp : mp) {
		// 	cerr << pp.first << " " << pp.second << endl;
		// }
	}
	for (auto pp : mp) {
		chkmin(ans, pp.first + pp.second);
	}
	if (ans == INF) {
		ans = -1;
	}
	return ans;
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = _x.size();
	x.resize(n);
	h.resize(n);
	for (int i = 0; i < n; ++i) {
		x[i] = (ll)_x[i];
		h[i] = (ll)_h[i];
	}
	m = l.size();
	for (int i = 0; i < m; ++i) {
		E.push_back({l[i], r[i], y[i]});
	}
	ll res = solve(s, g);
	return res;
}

Compilation message (stderr)

walk.cpp: In function 'long long int solve(int, int)':
walk.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bridge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i = 0; i < E.size(); ++i) {
      |                  ~~^~~~~~~~~~

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