oj.uz

Submission #610881

# Submission time Handle Problem Language Result Execution time Memory
610881 2022-07-28T17:02:38 Z fvogel499 Sky Walking (IOI19_walk) C++17
0 / 100
 262 ms 35152 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define int long long
#define size(x) (int)((x).size())

const int inf = 1e18;

int min_distance(std::vector<signed> pos, std::vector<signed> heightOf, std::vector<signed> leftP, std::vector<signed> rightP, std::vector<signed> yLevel, signed s, signed g) {
	const int n = size(pos);
	const int nbP = size(leftP);
	vector<int> finishAt [n];
	for (int i = 0; i < nbP; i++) {
		finishAt[rightP[i]].push_back(yLevel[i]);
	}
	finishAt[0].push_back(0);
	map<int, int> dp [n];
	for (int i : finishAt[n-1]) {
		dp[n-1][i] = i;
	}
	vector<pair<int, int>> addAt [n];
	vector<pair<int, int>> removeAt [n];
	for (int i = 0; i < nbP; i++) {
		addAt[rightP[i]].push_back({yLevel[i], rightP[i]});
		removeAt[leftP[i]].push_back({yLevel[i], rightP[i]});
	}
	map<int, int> m;
	for (int i = n-1; i >= 0; i--) {
		if (i < n-1) {
			for (int j : finishAt[i]) {
				dp[i][j] = inf;
				auto it = m.upper_bound(j);
				if (!m.empty() && it != m.end()) {
					int loc = dp[it->second][it->first]+it->first-j;
					dp[i][j] = min(dp[i][j], loc);
				}
				if (!m.empty() && it != m.begin()) {
					it = prev(it);
					int loc = dp[it->second][it->first]+j-it->first;
					dp[i][j] = min(dp[i][j], loc);
				}
			}
		}
		for (auto j : removeAt[i]) {
			assert(m.count(j.f));
			m.erase(j.f);
		}
		for (auto j : addAt[i]) {
			assert(!m.count(j.f));
			m[j.f] = j.s;
		}
	}
	int res = dp[0][0];
	res += (int)(pos[n-1]-pos[0]);
	return res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9104 KB Output is correct
2 Correct 151 ms 14276 KB Output is correct
3 Correct 159 ms 16392 KB Output is correct
4 Correct 199 ms 29772 KB Output is correct
5 Correct 262 ms 35152 KB Output is correct
6 Correct 255 ms 30944 KB Output is correct
7 Correct 89 ms 22300 KB Output is correct
8 Correct 125 ms 31612 KB Output is correct
9 Correct 249 ms 32684 KB Output is correct
10 Correct 143 ms 31956 KB Output is correct
11 Incorrect 13 ms 6868 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9104 KB Output is correct
2 Correct 151 ms 14276 KB Output is correct
3 Correct 159 ms 16392 KB Output is correct
4 Correct 199 ms 29772 KB Output is correct
5 Correct 262 ms 35152 KB Output is correct
6 Correct 255 ms 30944 KB Output is correct
7 Correct 89 ms 22300 KB Output is correct
8 Correct 125 ms 31612 KB Output is correct
9 Correct 249 ms 32684 KB Output is correct
10 Correct 143 ms 31956 KB Output is correct
11 Incorrect 13 ms 6868 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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