Submission #622599

#	Time	Username	Problem	Language	Result	Execution time	Memory
622599		cheissmart	Sky Walking (IOI19_walk)	C++14	0 / 100	25 ms	7892 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define MP make_pair
#define EB emplace_back
#define PB push_back
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;

vi asr[N], asl[N];

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	int n = SZ(x);
	if(s != 0 || g != n - 1) return 0LL;

	int m = SZ(l);
	for(int i = 0; i < m; i++) {
		asl[l[i]].PB(y[i]);
		asr[r[i]].PB(y[i]);
	}
	map<int, ll> mp;
	mp[0] = 0;
	asr[0].PB(0);

	for(int i = 0; i < n; i++) {
		set<int> no;
		for(int yy:asl[i]) {
			no.insert(yy);
			auto it = mp.lower_bound(yy);
			ll d = oo;
			if(it != mp.end()) 
				d = min(d, it -> S + abs(yy - it -> F));
			if(it != mp.begin()) {
				it--;
				d = min(d, it -> S + abs(yy - it -> F));
			}
			mp[yy] = d;
		}
		if(i < n - 1) for(int yy:asr[i]) {
			if(no.count(yy)) continue;
			mp.erase(yy);
		}
		if(mp.empty()) return -1;
	}

	ll ans = oo;
	for(auto[yy, d]:mp)
		ans = min(ans, d + yy);
	return ans + x[n - 1];
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(vi, vi, vi, vi, vi, int, int)':
walk.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |  for(auto[yy, d]:mp)
      |          ^

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