제출 #1242455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242455		nvujica	Sky Walking (IOI19_walk)	C++20	33 / 100	127 ms	17712 KiB

walk

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#include "walk.h"

using namespace std;

const int maxn = 1e5 + 10;
const ll inf = (1LL << 60);

vector<int> poc[maxn];
vector <int> kraj[maxn];
set <pair<int, ll> > s;
map<int, int> mp;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int g) {
	int n = x.size();
	int m = l.size();
	
	ll ans = x[n - 1] - x[0];

	for(int i = 0; i < m; i++){
		poc[l[i]].push_back(y[i]);
		kraj[r[i]].push_back(y[i]);
	}

	s.insert({0, 0});
	kraj[0].push_back(0);

	// for(int i = 0; i < poc[0].size(); i++){
	// 	int vis = poc[0][i];
		
	// 	s.insert({vis, vis});
	// }

	for(int i = 0; i < n - 1; i++){
		// cout << "tui " << i << ' ' << s.size() << endl;

		if(s.empty()) return -1;

		mp.clear();

		for(int j = 0; j < poc[i].size(); j++){
			int vis = poc[i][j];

			// if(mp.find(vis) != mp.end()){
			// 	s.insert({vis, mp[vis]});
			// 	continue;
			// }
			
			ll cost = inf;

			auto it = s.lower_bound({vis, 0});

			if(it != s.end() && (*it).fi == vis){
				mp[vis] = 1;
				continue;
			}
			if(it != s.end() && (*it).fi <= h[i]) cost = (*it).se + (*it).fi - vis;
			if(it != s.begin()){
				it--;
				cost = min(cost, (*it).se + vis - (*it).fi);
			}
			s.insert({vis, cost});
			//cout << "insert: " << vis << ' ' << cost << endl;
		}

		for(int j = 0; j < kraj[i].size(); j++){
			int vis = kraj[i][j];

			auto it = s.lower_bound({vis, 0});
			ll cost = (*it).se;
			// mp[vis] = cost;

			it++;
			if(it != s.end() && (*it).fi <= h[i]){
				ll c = cost + (*it).fi - vis;
				
				if(c < (*it).se){
					int vis2 = (*it).fi;
					s.erase(it);
					s.insert({vis2, c});
				}
				// (*it).se = min((*it).se, cost + (*it).fi - vis);
			}
			
			it = s.lower_bound({vis, 0});
			
			if(it != s.begin()){
				it--;
				ll c = cost + vis - (*it).fi;

				//(*it).se = min((*it).se, cost + vis - (*it).fi);
				if(c < (*it).se){
					int vis2 = (*it).fi;
					s.erase(it);
					s.insert({vis2, c});
				}
				
				it++;
			}

			if(mp[vis] == 0){
				//cout << "erase: " << vis << ' ' << cost << endl;
				s.erase({vis, cost});
			}
		}
	}

	if(s.empty()) return -1;

	ll naj = inf;

	auto it = s.begin();

	while(it != s.end()){
		naj = min(naj, (*it).fi + (*it).se);
		it++;
	}

	return ans + naj;
}

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