oj.uz

Submission #596713

# Submission time Handle Problem Language Result Execution time Memory
596713 2022-07-15T01:49:22 Z Temmie Sky Walking (IOI19_walk) C++17
0 / 100
 42 ms 6324 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::map <int, std::vector <int>> ind_seg_start_here;
	std::map <int, std::vector <int>> ind_seg_end_here;
	for (int i = 0; i < m; i++) {
		ind_seg_start_here[a[l[i]]].push_back(i);
		ind_seg_end_here[a[r[i]]].push_back(i);
	}
	std::map <int, std::map <int, long long>> arrive;
	std::map <int, int> active;
	arrive[0][0] = 0;
	std::set <int> idx;
	for (int x : a) {
		idx.insert(x);
	}
	for (int i : idx) {
		for (int x : ind_seg_end_here[i]) {
			active.erase(y[x]);
		}
		for (int x : ind_seg_start_here[i]) {
			active[y[x]] = x;
		}
		for (auto p : arrive[i]) {
			auto it = active.lower_bound(p.first);
			if (it != active.end()) {
				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
				if (itt == arrive[a[r[it->second]]].end() ||
				itt->second > p.second + abs(p.first - y[it->second])) {
					arrive[a[r[it->second]]][y[it->second]] =
					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
				}
			}
			it = active.upper_bound(p.first);
			if (it != active.begin()) {
				it--;
				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
				if (itt == arrive[a[r[it->second]]].end() ||
				itt->second > p.second + abs(p.first - y[it->second])) {
					arrive[a[r[it->second]]][y[it->second]] =
					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
				}
			}
		}
	}
	long long ans = 1LL << 60;
	for (auto p : arrive[a[n - 1]]) {
		ans = std::min(ans, p.second + p.first);
	}
	return ans;
}

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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 6324 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 -