Submission #285981

#	Time	Username	Problem	Language	Result	Execution time	Memory
285981		cookiedoth	Sky Walking (IOI19_walk)	C++14	57 / 100	4046 ms	304376 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 min_st {
	min_st() {}

	vector<pair<ll, int> > t;
	int n;

	void build(const vector<ll> &h, int v, int tl, int tr) {
		if (tl == tr) {
			t[v] = {h[tl], tl};
		} else {
			int tm = (tl + tr) >> 1;
			build(h, v * 2, tl, tm);
			build(h, v * 2 + 1, tm + 1, tr);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	void init(const vector<ll> &h) {
		n = h.size();
		t.resize(4 * n);
		build(h, 1, 0, n - 1);
	}

	pair<ll, int> get(int l, int r, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return {-1, -1};
		}
		if (l <= tl && tr <= r) {
			return t[v];
		} else {
			int tm = (tl + tr) >> 1;
			pair<ll, int> res_l = get(l, r, v * 2, tl, tm);
			pair<ll, int> res_r = get(l, r, v * 2 + 1, tm + 1, tr);
			return max(res_l, res_r);
		}
	}

	pair<ll, int> get(int l, int r) {
		pair<ll, int> res = get(l, r, 1, 0, n - 1);
		return res;
	}
};

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;
}

namespace djkstra_sol {
	vector<vector<ll> > good_y;
	vector<vector<pair<int, int> > > fwd, bck;
	min_st T;

	void add(int l, int r, ll x, vector<int> &res) {
		if (l > r) {
			return;
		}
		pair<ll, int> opt = T.get(l, r);
		// cerr << "opt = " << opt.first << " " << opt.second << endl;
		if (opt.first >= x) {
			// cerr << "add " << opt.second << endl;
			res.push_back(opt.second);
			add(l, opt.second - 1, x, res);
			add(opt.second + 1, r, x, res);
		}
	}

	vector<int> find_x(bridge B) {
		// cerr << "find_x " << B.l << " " << B.r << " " << B.y << endl;
		vector<int> res;
		add(B.l, B.r, B.y, res);
		return res;
	}

	vector<vector<int> > xc;

	void build_xc(int s, int g) {
		T.init(h);
		// output(all(h));
		// cerr << "sg = " << s << " " << g << endl;
		xc.resize(m);
		good_y.resize(n);
		for (int i = 0; i < m; ++i) {
			xc[i] = find_x(E[i]);
			sort(all(xc[i]));
			for (auto id : xc[i]) {
				good_y[id].push_back(E[i].y);
			}
		}
		good_y[s].push_back(0);
		good_y[g].push_back(0);
		for (int i = 0; i < n; ++i) {
			sort(all(good_y[i]));
			good_y[i].erase(unique(all(good_y[i])), good_y[i].end());
		}
	}

	void build_graph() {
		fwd.resize(n);
		bck.resize(n);
		for (int i = 0; i < n; ++i) {
			fwd[i].resize(good_y[i].size(), make_pair(-1, -1));
			bck[i].resize(good_y[i].size(), make_pair(-1, -1));
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < (int)xc[i].size() - 1; ++j) {
				int l = xc[i][j], r = xc[i][j + 1];
				int pl = lower_bound(all(good_y[l]), E[i].y) - good_y[l].begin();
				int pr = lower_bound(all(good_y[r]), E[i].y) - good_y[r].begin();
				fwd[l][pl] = {r, pr};
				bck[r][pr] = {l, pl};
			}
		}
	}

	const ll INF = 1e18;
	vector<vector<ll> > d;
	vector<vector<int> > used;

	void djkstra(int s) {
		d.resize(n);
		used.resize(n);
		for (int i = 0; i < n; ++i) {
			d[i].resize(good_y[i].size(), INF);
			used[i].resize(good_y[i].size(), 0);
		}
		set<pair<ll, pair<int, int> > > S;
		d[s][0] = 0;
		S.insert({0, {s, 0}});
		vector<pair<ll, pair<int, int> > > go;
		while (!S.empty()) {
			int id = S.begin()->second.first;
			int level = S.begin()->second.second;
			S.erase(S.begin());
			if (used[id][level]) {
				continue;
			}
			used[id][level] = 1;
			go.clear();
			if (fwd[id][level] != make_pair(-1, -1)) {
				go.emplace_back(x[fwd[id][level].first] - x[id], fwd[id][level]);
			}
			if (bck[id][level] != make_pair(-1, -1)) {
				go.emplace_back(x[id] - x[bck[id][level].first], bck[id][level]);
			}
			if (level < (int)good_y[id].size() - 1) {
				go.emplace_back(good_y[id][level + 1] - good_y[id][level], make_pair(id, level + 1));
			}
			if (level > 0) {
				go.emplace_back(good_y[id][level] - good_y[id][level - 1], make_pair(id, level - 1));
			}
			for (auto ppp : go) {
				if (chkmin(d[ppp.second.first][ppp.second.second], d[id][level] + ppp.first)) {
					S.insert({d[ppp.second.first][ppp.second.second], ppp.second});
				}
			}
		}
	}

	ll solve(int s, int g) {
		build_xc(s, g);
		// cerr << "build_xc" << endl;			
		build_graph();
		djkstra(s);
		return (d[g][0] == INF ? -1 : d[g][0]);
	}
}

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;
	if (s == 0 && g == n - 1) {
		res = solve(s, g);
	} else {
		res = djkstra_sol::solve(s, g);
	}
	return res;
}

Compilation message (stderr)

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

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