oj.uz

Submission #817068

# Submission time Handle Problem Language Result Execution time Memory
817068 2023-08-09T09:02:43 Z vjudge1 Sky Walking (IOI19_walk) C++17
0 / 100
 13 ms 2620 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -