oj.uz

Submission #422774

# Submission time Handle Problem Language Result Execution time Memory
422774 2021-06-10T12:06:52 Z KoD Sky Walking (IOI19_walk) C++17
0 / 100
 206 ms 19476 KB 
#include <bits/stdc++.h>
#include "walk.h"

using ll = long long;
template <class T> using Vec = std::vector<T>;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

struct RMQ {
	int size;
	Vec<ll> min;
	RMQ(const int n): size(n), min(2 * n, INF) {}
	void assign(int i, const ll x) {
		i += size;
		min[i] = x;
		while (i > 1) {
			i >>= 1;
			min[i] = std::min(min[2 * i], min[2 * i + 1]);
		}
	}
	ll fold(int l, int r) const {
		l += size;
		r += size;
		ll x = INF;
		while (l < r) {
			if (l & 1) x = std::min(x, min[l++]);
			if (r & 1) x = std::min(x, min[--r]);
			l >>= 1;
			r >>= 1;
		}
		return x;
	}
};

ll min_distance(Vec<int> x, Vec<int> h, Vec<int> l, Vec<int> r, Vec<int> y, int s, int g) {
	const int n = (int) x.size();
	const int m = (int) y.size();
	if (s == 0 and g == n - 1) {
		Vec<Vec<int>> start(n), end(n);
		for (int i = 0; i < m; ++i) {
			start[l[i]].push_back(i);
			end[r[i]].push_back(i);
		}
		Vec<int> cmp = y;
		std::sort(cmp.begin(), cmp.end());
		cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
		Vec<int> idx(m);
		for (int i = 0; i < m; ++i) {
			idx[i] = std::lower_bound(cmp.begin(), cmp.end(), y[i]) - cmp.begin();
		}
		const int sz = (int) cmp.size();
		RMQ down(sz), up(sz);
		Vec<int> alive(sz);
		for (const int j: start[0]) {
			down.assign(idx[j], y[j] - y[j]);
			up.assign(idx[j], y[j] + y[j]);
			alive[idx[j]] += 1;			
		}
		for (int i = 1; i < n; ++i) {
			const int height = std::upper_bound(cmp.begin(), cmp.end(), h[i]) - cmp.begin();
			for (const auto j: start[i]) {
				const ll d = std::min(y[j] + down.fold(0, idx[j] + 1), up.fold(idx[j], height) - y[j]);				
				down.assign(idx[j], d - y[j]);
				up.assign(idx[j], d + y[j]);
				alive[idx[j]] += 1;
			}
			if (i != n - 1) {
				for (const auto j: end[i]) {
					alive[idx[j]] -= 1;
					if (alive[idx[j]] == 0) {
						down.assign(idx[j], INF);
						up.assign(idx[j], INF);
					}
				}
			}
		}
		ll ret = up.fold(0, sz);
		return ret == INF / 2 ? -1 : (ret + x[n - 1] - x[0]);
	}
	return -1;
}

Subtask #1
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3396 KB Output is correct
2 Correct 122 ms 8128 KB Output is correct
3 Correct 131 ms 9148 KB Output is correct
4 Correct 203 ms 17136 KB Output is correct
5 Correct 170 ms 15556 KB Output is correct
6 Correct 204 ms 16980 KB Output is correct
7 Correct 126 ms 12740 KB Output is correct
8 Correct 206 ms 19476 KB Output is correct
9 Correct 206 ms 18092 KB Output is correct
10 Correct 124 ms 14912 KB Output is correct
11 Incorrect 18 ms 3404 KB Output isn't correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3396 KB Output is correct
2 Correct 122 ms 8128 KB Output is correct
3 Correct 131 ms 9148 KB Output is correct
4 Correct 203 ms 17136 KB Output is correct
5 Correct 170 ms 15556 KB Output is correct
6 Correct 204 ms 16980 KB Output is correct
7 Correct 126 ms 12740 KB Output is correct
8 Correct 206 ms 19476 KB Output is correct
9 Correct 206 ms 18092 KB Output is correct
10 Correct 124 ms 14912 KB Output is correct
11 Incorrect 18 ms 3404 KB Output isn't correct

Subtask #5
0 / 43.0

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