제출 #1222784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222784		HappyCapybara	Sky Walking (IOI19_walk)	C++17	100 / 100	3212 ms	459928 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<pair<int,int>> hs;
	sort(ev.begin(), ev.end());
	int i = 0;
	while (i < (int)ev.size()){
		int ct = ev[i][0];
		set<pair<int,int>> rm, in;
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == -1){
			hs.erase({y[ev[i][2]], ev[i][2]});
			rm.insert({y[ev[i][2]], ev[i][2]});
            i++;
		}
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == 1){
			hs.insert({y[ev[i][2]], ev[i][2]});
			in.insert({y[ev[i][2]], ev[i][2]});
            i++;
		}
		for (auto it=rm.begin(); it != rm.end(); it++){
			auto jt = hs.upper_bound({it->first+1, -1});
			if (jt != hs.end()) cp[it->second].push_back(jt->second);
			if (jt != hs.begin()){
				jt--;
				cp[it->second].push_back(jt->second);
				if (jt->first == it->first && jt != hs.begin()){
					jt--;
					cp[it->second].push_back(jt->second);
				}
			}
			if (next(it) != rm.end()) cp[it->second].push_back(next(it)->second);
		}
		for (auto it=in.begin(); it != in.end(); it++){
			auto jt = hs.upper_bound({it->first+1, -1});
			if (jt != hs.end()) cp[it->second+m].push_back(jt->second);
			if (jt != hs.begin()){
				jt--;
				cp[it->second+m].push_back(jt->second);
				if (jt->first == it->first && jt != hs.begin()){
					jt--;
					cp[it->second+m].push_back(jt->second);
				}
			}
			if (next(it) != in.end()) cp[it->second+m].push_back(next(it)->second);
		}
	}
	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: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43