Submission #951008

#	Time	Username	Problem	Language	Result	Execution time	Memory
951008		Trisanu_Das	Sky Walking (IOI19_walk)	C++17	57 / 100	4051 ms	538576 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define MP make_pair
#define EB emplace_back
#define PB push_back
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;
 
vi asr[N], asl[N];
map<int, ll> dist[N];
map<int, vi> js[N];
vi ys[N], ks[N];
 
ll brute(vi& x, vi& h, vi& l, vi& r, vi& y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
 
	ys[s].PB(0);
	ys[g].PB(0);
 
	auto add_ev = [&] (int i, int j) {
		js[i][y[j]].PB(j);
		ys[i].PB(y[j]);
		ks[j].PB(i);
	};
 
	vi sh(n); iota(ALL(sh), 0);
	sort(ALL(sh), [&] (int i, int j) {
		return h[i] < h[j];
	});
	vi sy(m); iota(ALL(sy), 0);
	sort(ALL(sy), [&] (int i, int j) {
		return y[i] < y[j];
	});
	set<int> st;
	while(SZ(sy)) {
		int j = sy.back(); sy.pop_back();
		while(SZ(sh) && h[sh.back()] >= y[j]) {
			st.insert(sh.back());
			sh.pop_back();
		}
		auto it = st.lower_bound(l[j]);
		while(it != st.end() && *it <= r[j]) {
			add_ev(*it, j);
			it++;
		}
	}
 
	for(int i = 0; i < n; i++) {
		sort(ALL(ys[i]));
		ys[i].resize(unique(ALL(ys[i])) - ys[i].begin());
	}
 
	auto get_edges = [&] (int i, int yy) {
		V<pair<pi, int>> res;
		int pos = lower_bound(ALL(ys[i]), yy) - ys[i].begin();
		for(int _ = max(pos - 1, 0); _ <= min(pos + 1, SZ(ys[i]) - 1); _++) {
			int yyy = ys[i][_];
			res.EB(pi(i, yyy), abs(yy - yyy));
		}
		for(int j:js[i][yy]) {
			for(int k:ks[j]) {
				res.EB(pi(k, yy), abs(x[i] - x[k]));
			}
		}
		return res;
	};
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(0, pi(s, 0)));
	dist[s][0] = 0;
	
	while(pq.size()) {
		auto[dd, state] = pq.top(); pq.pop();
		auto[i, yy] = state;
		if(dd > dist[i][yy]) continue;
		V<pair<pi, int>> res = get_edges(i, yy);
		for(auto[nstate, w]:res) {
			auto[ni, nyy] = nstate;
			if(dist[ni].count(nyy) == 0 || dd + w < dist[ni][nyy]) {
				dist[ni][nyy] = dd + w;
				pq.push(MP(dd + w, nstate));
			}
		}
	}
 
	if(dist[g].count(0))
		return dist[g][0];
	return -1;
}
 
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
	if(s != 0 || g != n - 1) {
		return brute(x, h, l, r, y, s, g);
	}
 
	for(int i = 0; i < m; i++) {
		asl[l[i]].PB(y[i]);
		asr[r[i]].PB(y[i]);
	}
	map<int, ll> mp;
	mp[0] = 0;
	asr[0].PB(0);
 
	for(int i = 0; i < n; i++) {
		set<int> no;
		for(int yy:asl[i]) {
			no.insert(yy);
			auto it = mp.lower_bound(yy);
			ll d = oo;
			if(it != mp.end()) 
				d = min(d, it -> S + abs(yy - it -> F));
			if(it != mp.begin()) {
				it--;
				d = min(d, it -> S + abs(yy - it -> F));
			}
			mp[yy] = d;
		}
		if(i < n - 1) for(int yy:asr[i]) {
			if(no.count(yy)) continue;
			mp.erase(yy);
		}
		if(mp.empty()) return -1;
	}
 
	ll ans = oo;
	for(auto[yy, d]:mp)
		ans = min(ans, d + yy);
	return ans + x[n - 1] - x[0];
}

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