Submission #817068

#	Time	Username	Problem	Language	Result	Execution time	Memory
817068		vjudge1	Sky Walking (IOI19_walk)	C++17	0 / 100	13 ms	2620 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
pii tree[4  * 100100];
void update(int node, int l, int r, int pos, int val){
	if(l == r)	tree[node] = mp(val - pos + 1, pos);
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update(node*2, l, mid, pos, val);
		else update(node*2+1, mid+1, r, pos, val);
		
		tree[node] = min(tree[node*2], tree[node*2+1]);
	}
}
pii query(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return mp(1e9, 1e9);
	if(L <= l && r <= R)	return tree[node];
	
	int mid = (l + r) / 2;
	return min(query(node*2, l, mid, L, R), query(node*2+1, mid+1, r, L, R));
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n = (int)x.size();
	for(int i = 0; i < n; i++)	update(1, 0, n-1, i, 1e9);
	update(1, 0, n-1, 0, 0);
	int best_left[n];
	for(int i = 0; i < n; i++)	best_left[i] = i;
	for(int i = 0; i < (int)r.size(); i++){
		best_left[r[i]] = min(best_left[r[i]], l[i]);
	}
	ll dp[n];
	memset(dp, 1e9, sizeof dp);
	dp[0] = 0;
	for(int i = 1; i < n; i++){
		auto prasaj = query(1, 0, n-1, best_left[i], i);
		dp[i] = prasaj.first + i;
		update(1, 0, n-1, i, dp[i]);
		
	}
	return dp[n-1] + h[0] + h[n-1];
}

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