oj.uz

Submission #596716

# Submission time Handle Problem Language Result Execution time Memory
596716 2022-07-15T01:57:07 Z Temmie Sky Walking (IOI19_walk) C++17
15 / 100
 157 ms 20132 KB 
#include <bits/stdc++.h>

long long min_distance(std::vector <int> a, std::vector <int> h,
std::vector <int> l, std::vector <int> r, std::vector <int> y,
int s, int e) {
	if (e < s) {
		std::swap(s, e);
	}
	int n = a.size();
	int m = y.size();
	std::vector <std::vector <std::pair <int, bool>>> inds(n + 1);
	for (int i = 0; i < m; i++) {
		inds[l[i]].emplace_back(y[i], true);
		inds[r[i] + 1].emplace_back(y[i], false);
	}
	inds[1].emplace_back(0, false);
	std::map <int, long long> mp;
	mp[0] = 0;
	std::set <int> st;
	for (int i = 0; i < n; i++) {
		for (auto p : inds[i]) {
			if (!p.second && !st.count(p.first)) {
				mp.erase(p.first);
			}
		}
		st.clear();
		for (auto p : inds[i]) {
			if (p.second) {
				auto it = mp.lower_bound(p.first);
				long long val = 1LL << 60;
				if (it != mp.end()) {
					val = std::min(val, it->second - p.first + it->first);
				}
				if (it != mp.begin()) {
					it--;
					val = std::min(val, it->second - it->first + p.first);
				}
				mp[p.first] = val;
				st.insert(p.first);
			}
		}
	}
	if (mp.empty()) {
		return -1;
	}
	return mp.begin()->first + mp.begin()->second + a[n - 1] - a[0];
}

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3284 KB Output is correct
2 Correct 94 ms 6864 KB Output is correct
3 Correct 114 ms 7944 KB Output is correct
4 Correct 132 ms 14460 KB Output is correct
5 Correct 157 ms 20132 KB Output is correct
6 Correct 141 ms 16716 KB Output is correct
7 Correct 78 ms 10700 KB Output is correct
8 Correct 81 ms 13632 KB Output is correct
9 Correct 126 ms 17192 KB Output is correct
10 Correct 124 ms 16556 KB Output is correct
11 Correct 11 ms 2992 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3284 KB Output is correct
2 Correct 94 ms 6864 KB Output is correct
3 Correct 114 ms 7944 KB Output is correct
4 Correct 132 ms 14460 KB Output is correct
5 Correct 157 ms 20132 KB Output is correct
6 Correct 141 ms 16716 KB Output is correct
7 Correct 78 ms 10700 KB Output is correct
8 Correct 81 ms 13632 KB Output is correct
9 Correct 126 ms 17192 KB Output is correct
10 Correct 124 ms 16556 KB Output is correct
11 Correct 11 ms 2992 KB Output is correct
12 Correct 94 ms 7924 KB Output is correct
13 Incorrect 122 ms 14392 KB Output isn't correct
14 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 -