제출 #1050151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050151		Kel_Mahmut	Sky Walking (IOI19_walk)	C++17	0 / 100	121 ms	15700 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = l.size();
	ll ans = LLONG_MAX;
	bool st3 = (s == 0) && (g == n - 1);
	for(int i = 0; i < n; i++)
		st3 &= h[i] == h[0];
	if(st3){
		set<pair<ll, ll>> act;
		vector<set<pair<ll, ll>>> skywalks(n);
		for(int i = 0; i < m; i++){
			skywalks[l[i]].insert(make_pair(y[i], 0));
		}
		for(int i = 0; i < m; i++){
			auto it = skywalks[r[i]].lower_bound(make_pair(y[i], -1));
			if(it != skywalks[r[i]].end() && it->first == y[i]){
				skywalks[r[i]].erase(it);
			}
			else{
				skywalks[r[i]].insert(make_pair(y[i], 1));
			}
		}

		for(auto [a, b] : skywalks[0]){
			act.insert({b, b});
		}

		for(int i = 0; i < n; i++){
			for(auto [a, b] : skywalks[i]){
				if(b == 0){
					ll minh = 1e16;
					auto it = act.lower_bound(make_pair(a, -1));
					if(it != act.end()){
						minh = min(minh, it->second + abs(a - it->first));
					}
					if(it != act.begin()){
						it = prev(it);
						minh = min(minh, it->second + abs(a - it->first));
					}
					act.insert(make_pair(a, minh));
				}
				else{
					auto it = act.lower_bound(make_pair(a, -1));
					ll cur = it->second;
					if(i == n - 1){
						ans = min(ans, cur + a);
					}
					assert(it->first == a);
					act.erase(it);
					it = act.lower_bound(make_pair(a, -1));
					if(it != act.end()){
						ll curheight = it->first;
						ll minh = min(it->second, cur + abs(it->first - a));
						act.erase(it);
						act.insert(make_pair(curheight, minh));
					}
					it = act.lower_bound(make_pair(a, -1));
					if(it != act.begin()){
						it = prev(it);
						ll curheight = it->first;
						ll minh = min(it->second, cur + abs(curheight - a));
						act.erase(it);
						act.insert(make_pair(curheight, minh));
					}
				}
			}
		}
		return ans + x[g] - x[s];
	}
	return 0;
}

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