Submission #285970

#	Time	Username	Problem	Language	Result	Execution time	Memory
285970		cookiedoth	Sky Walking (IOI19_walk)	C++14	0 / 100	4056 ms	5364 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;
		for (int i = 0; i < n; ++i) {
			assert(i <= 10000);
			sort(all(events[i]));
			for (auto pp : events[i]) {
				// cerr << "pp " << pp.first << " " << pp.second << endl;
				ll y = pp.second;
				new_chel.clear();
				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);
					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:21: 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: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43