Submission #298496

#	Time	Username	Problem	Language	Result	Execution time	Memory
298496		JPN20	Sky Walking (IOI19_walk)	C++17	15 / 100	242 ms	33144 KiB

walk

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

// Input
long long N, X[1 << 18], H[1 << 18];
long long M, L[1 << 18], R[1 << 18], Y[1 << 18];
long long SX, GX;

// Compress
vector<pair<int, int>> V[1 << 18][2];
set<tuple<int, int, long long>> Set;

void add(int height, int idx, int lim) {
	auto itr = Set.lower_bound(make_tuple(height, idx, 0LL));
	long long res = (1LL << 60);
	if (itr != Set.end()) {
		tuple<int, int, long long> val1 = (*itr);
		if (get<0>(val1) <= lim) res = min(res, get<2>(val1) + abs(height - get<0>(val1))); 
	}
	if (itr != Set.begin()) {
		itr--;
		tuple<int, int, long long> val2 = (*itr);
		if (get<0>(val2) <= lim) res = min(res, get<2>(val2) + abs(height - get<0>(val2))); 
	}
	Set.insert(make_tuple(height, idx, res));
}	

void lose(int height, int idx) {
	auto itr = Set.lower_bound(make_tuple(height, idx, 0LL));
	Set.erase(itr);
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	N = x.size();
	M = l.size();
	SX = s;
	GX = g;
	for (int i = 0; i < N; i++) X[i] = x[i];
	for (int i = 0; i < N; i++) H[i] = h[i];
	for (int i = 0; i < M; i++) L[i] = l[i];
	for (int i = 0; i < M; i++) R[i] = r[i];
	for (int i = 0; i < M; i++) Y[i] = y[i];
	
	// Step #1. Maeshori
	V[0][1].push_back(make_pair(0, -1));
	for (int i = 0; i < M; i++) V[L[i]][0].push_back(make_pair(Y[i], i));
	for (int i = 0; i < M; i++) V[R[i]][1].push_back(make_pair(Y[i], i));
	for (int i = 0; i < N; i++) sort(V[i][0].begin(), V[i][0].end());
	for (int i = 0; i < N; i++) sort(V[i][1].begin(), V[i][1].end());
	
	// Step #2. Compress
	Set.insert(make_tuple(0, -1, 0LL));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < (int)V[i][0].size(); j++) add(V[i][0][j].first, V[i][0][j].second, H[i]);
		if (i == N - 1) break;
		for (int j = 0; j < (int)V[i][1].size(); j++) lose(V[i][1][j].first, V[i][1][j].second);
	}
	
	// Step #3. Get Answer
	long long Answer = (1LL << 60);
	auto itr = Set.begin();
	while (itr != Set.end()) {
		Answer = min(Answer, get<0>(*itr) + get<2>(*itr));
		itr++;
	}
	
	// Step #4. Output
	if (Answer == (1LL << 60)) return -1;
	return Answer + (X[N - 1] - X[0]);
}

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