oj.uz

Submission #610880

# Submission time Handle Problem Language Result Execution time Memory
610880 2022-07-28T17:00:19 Z fvogel499 Sky Walking (IOI19_walk) C++17
0 / 100
 264 ms 39116 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 += pos[n-1]-pos[0];
	return res;
}

Subtask #1
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9772 KB Output is correct
2 Correct 157 ms 16124 KB Output is correct
3 Correct 165 ms 18432 KB Output is correct
4 Correct 200 ms 33816 KB Output is correct
5 Correct 264 ms 39116 KB Output is correct
6 Correct 246 ms 34864 KB Output is correct
7 Correct 89 ms 25220 KB Output is correct
8 Correct 174 ms 35512 KB Output is correct
9 Correct 244 ms 36824 KB Output is correct
10 Correct 132 ms 35316 KB Output is correct
11 Incorrect 12 ms 7720 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9772 KB Output is correct
2 Correct 157 ms 16124 KB Output is correct
3 Correct 165 ms 18432 KB Output is correct
4 Correct 200 ms 33816 KB Output is correct
5 Correct 264 ms 39116 KB Output is correct
6 Correct 246 ms 34864 KB Output is correct
7 Correct 89 ms 25220 KB Output is correct
8 Correct 174 ms 35512 KB Output is correct
9 Correct 244 ms 36824 KB Output is correct
10 Correct 132 ms 35316 KB Output is correct
11 Incorrect 12 ms 7720 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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