제출 #1155712

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

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
#define pq priority_queue
const int N = 2e6 + 5, INF = 1e18;

int n, m;
arr<set<int>, N> ins, dlt;

int min_distance(vec<sig> _x, vec<sig> _h, vec<sig> _l, vec<sig> _r, vec<sig> _y, sig _s, sig _f) {
	n = _x.size(), m = _l.size();
	int ans = 0;
	for (int i = 0; i < n - 1; i++) ans += _x[i + 1] - _x[i];

	for (int i = 0; i < m; i++) {
		ins[_l[i]].insert(_y[i]);
		dlt[_r[i]].insert(_y[i]);
	}

	for (int i = 0; i < n; i++) {
		vec<int> x;
		for (int y : ins[i]) {
			if (dlt[i].count(y)) {
				dlt[i].erase(y);
				x.push_back(y);
			}
		}
		for (int y : x) ins[i].erase(y);
	}

	set<pii> pnt;
	for (int i = 0; i < n; i++) {
		// for (pii x : pnt) cout << x.fir << " " << x.sec << "  ";
		// cout << endl;

		for (int x : ins[i]) {
			int cst = (i == 0) ? x : INF;
			if (pnt.upper_bound({x, -1}) != pnt.begin()) {
				auto it = --pnt.upper_bound({x, -1});
				cst = min(cst, x - it->fir + it->sec);
			}
			if (pnt.upper_bound({x, -1}) != pnt.end()) {
				auto it = pnt.upper_bound({x, -1});
				cst = min(cst, it->fir - x + it->sec);
			}
			pnt.insert({x, cst});
		}
		if (i == n - 1) break;
		for (int x : dlt[i]) {
			auto it = pnt.upper_bound({x, -1});
			pnt.erase(it);
		}
	}

	int mn = INF;
	for (pii x : pnt) mn = min(mn, x.fir + x.sec);
	if (mn == INF) return -1;
	return ans + mn;
}

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