Submission #1222685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222685		HappyCapybara	Sky Walking (IOI19_walk)	C++17	43 / 100	1922 ms	169876 KiB

walk

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

#define ll long long

ll hf(ll x, ll y){
	return x*pow(10, 10)+y;
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	if (s > g) swap(s, g);
    int n = x.size();
	int m = l.size();
	int om = m;
	vector<int> sl(n, 0), sr(n, 0), gl(n, 0), gr(n, 0);
	sl[s] = h[s];
	for (int i=s-1; i>=0; i--) sl[i] = max(sl[i+1], h[i]);
	sr[s] = h[s];
	for (int i=s+1; i<n; i++) sr[i] = max(sr[i-1], h[i]);
	gl[g] = h[g];
	for (int i=g-1; i>=0; i--) gl[i] = max(gl[i+1], h[i]);
	gr[g] = h[g];
	for (int i=g+1; i<n; i++) gr[i] = max(gr[i-1], h[i]);
	for (int i=0; i<om; i++){
		vector<int> imp = {l[i], r[i]};
		if (l[i] < s && s < r[i]){
			int lo = l[i], hi = s+1;
			while (lo < hi-1){
				int mid = (lo+hi)/2;
				if (sl[mid] >= y[i]) lo = mid;
				else hi = mid;
			}
			int a = lo;
			lo = s-1, hi = r[i];
			while (lo < hi-1){
				int mid = (lo+hi)/2;
				if (sr[mid] >= y[i]) hi = mid;
				else lo = mid;
			}
			int b = hi;
			if (find(imp.begin(), imp.end(), a) == imp.end()) imp.push_back(a);
			if (find(imp.begin(), imp.end(), b) == imp.end()) imp.push_back(b);
		}
		if (l[i] < g && g < r[i]){
			int lo = l[i], hi = g+1;
			while (lo < hi-1){
				int mid = (lo+hi)/2;
				if (gl[mid] >= y[i]) lo = mid;
				else hi = mid;
			}
			int a = lo;
			lo = g-1, hi = r[i];
			while (lo < hi-1){
				int mid = (lo+hi)/2;
				if (gr[mid] >= y[i]) hi = mid;
				else lo = mid;
			}
			int b = hi;
			if (find(imp.begin(), imp.end(), a) == imp.end()) imp.push_back(a);
			if (find(imp.begin(), imp.end(), b) == imp.end()) imp.push_back(b);
		}
		sort(imp.begin(), imp.end());
		m += imp.size()-2;
		r[i] = imp[1];
		for (int j=1; j+1<(int)imp.size(); j++){
			l.push_back(imp[j]);
			r.push_back(imp[j+1]);
			y.push_back(y[i]);
		}
	}
	vector<vector<int>> cp(m*2), ip(m);
	vector<vector<int>> ev;
	for (int i=0; i<m; i++){
		ev.push_back({l[i], 1, i});
		ev.push_back({r[i], -1, i});
	}
	set<int> hs;
	map<int,int> htw;
	sort(ev.begin(), ev.end());
	int i = 0;
	while (i < (int)ev.size()){
		int ct = ev[i][0];
		set<int> rm, in;
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == -1){
			hs.erase(y[ev[i][2]]);
			rm.insert(ev[i][2]);
            i++;
		}
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == 1){
			hs.insert(y[ev[i][2]]);
			htw[y[ev[i][2]]] = ev[i][2];
			in.insert(ev[i][2]);
            i++;
		}
		for (int w : rm){
			auto it = hs.upper_bound(y[w]);
			if (it != hs.end()) cp[w].push_back(htw[*it]);
			if (it != hs.begin()){
				it--;
				cp[w].push_back(htw[*it]);
				if (*it == y[w] && it != hs.begin()){
					it--;
					cp[w].push_back(htw[*it]);
				}
			}
		}
		for (int w : in){
			auto it = hs.upper_bound(y[w]);
			if (it != hs.end()) cp[w+m].push_back(htw[*it]);
			if (it != hs.begin()){
				it--;
				cp[w+m].push_back(htw[*it]);
				if (*it == y[w] && it != hs.begin()){
					it--;
					cp[w+m].push_back(htw[*it]);
				}
			}
		}
	}
	map<ll,vector<pair<ll,ll>>> gh;
	for (int i=0; i<m; i++){
		ip[i].push_back(l[i]);
		ip[i].push_back(r[i]);
		for (int next : cp[i]){
			if (y[next] <= h[r[i]]) ip[next].push_back(r[i]);
		}
		for (int next : cp[i+m]){
			if (y[next] <= h[l[i]]) ip[next].push_back(l[i]);
		}
	}
	for (int i=0; i<m; i++){
		if (l[i] <= s && s <= r[i] && y[i] <= h[s]) gh[hf(s, 0)].push_back({hf(s, y[i]), y[i]});
		if (l[i] <= g && g <= r[i] && y[i] <= h[g]) gh[hf(g, y[i])].push_back({hf(g, 0), y[i]});
		sort(ip[i].begin(), ip[i].end());
		assert(ip[i][0] == l[i] && ip[i].back() == r[i]);
		for (int j=0; j+1<(int)ip[i].size(); j++){
			gh[hf(ip[i][j], y[i])].push_back({hf(ip[i][j+1], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
			gh[hf(ip[i][j+1], y[i])].push_back({hf(ip[i][j], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
		}
		for (int next : cp[i]){
			if (y[next] > h[r[i]]) continue;
			gh[hf(r[i], y[i])].push_back({hf(r[i], y[next]), abs(y[next]-y[i])});
			gh[hf(r[i], y[next])].push_back({hf(r[i], y[i]), abs(y[next]-y[i])});
		}
		for (int next : cp[i+m]){
			if (y[next] > h[l[i]]) continue;
			gh[hf(l[i], y[i])].push_back({hf(l[i], y[next]), abs(y[next]-y[i])});
			gh[hf(l[i], y[next])].push_back({hf(l[i], y[i]), abs(y[next]-y[i])});
		}
	}
	vector<int> lm, rm;
	for (int i=0; i<m; i++){
		if (l[i] == 0) lm.push_back(y[i]);
		if (r[i] == n-1) rm.push_back(y[i]);
	}
	sort(lm.begin(), lm.end());
	for (int j=0; j+1<(int)lm.size(); j++){
		gh[hf(0, lm[j])].push_back({hf(0, lm[j+1]), lm[j+1]-lm[j]});
		gh[hf(0, lm[j+1])].push_back({hf(0, lm[j]), lm[j+1]-lm[j]});
	}
	sort(rm.begin(), rm.end());
	for (int j=0; j+1<(int)rm.size(); j++){
		gh[hf(n-1, rm[j])].push_back({hf(n-1, rm[j+1]), rm[j+1]-rm[j]});
		gh[hf(n-1, rm[j+1])].push_back({hf(n-1, rm[j]), rm[j+1]-rm[j]});
	}
	priority_queue<pair<ll,ll>> pq;
	pq.push({0, hf(s, 0)});
	unordered_set<ll> seen;
	while (!pq.empty()){
		ll cur = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (seen.find(cur) != seen.end()) continue;
		seen.insert(cur);
		if (cur == hf(g, 0)) return d;
		for (pair<ll,ll> next : gh[cur]) pq.push({-(d+next.second), next.first});
	}
	return -1;
}

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