Submission #612878

#	Time	Username	Problem	Language	Result	Execution time	Memory
612878		Temmie	Shortcut (IOI16_shortcut)	C++17	97 / 100	2089 ms	47312 KiB

shortcut

#include <bits/stdc++.h>

constexpr const int mxn = 1'000'000;

long long her[2][mxn];
int ord[2][mxn];
long long pre[mxn];
int c, n;

bool check(long long mid, const std::vector <int>& d) {
	static long long corners[2][2];
	static long long hbb[2], hsbb[2], hwb[2];
	corners[0][0] = corners[0][1] = corners[1][0] = corners[1][1] = hbb[0] = hbb[1] = hsbb[0] = hsbb[1] = -(1LL << 60);
	hwb[0] = hwb[1] = -1;
	for (int i = 0, rb = n - 1; i < n; i++) {
		if (mid - 10 < static_cast <long long> (2e9)) {
			while (~rb && her[0][i] + her[1][rb] > mid) {
				for (int k = 0; k < 2; k++) {
					long long now = d[ord[1][rb]] + (k ? -pre[ord[1][rb]] : pre[ord[1][rb]]);
					if (now > hbb[k]) {
						hsbb[k] = hbb[k];
						hbb[k] = now;
						hwb[k] = ord[1][rb];
					} else if (now > hsbb[k]) {
						hsbb[k] = now;
					}
				}
				rb--;
			}
			for (int ii = 0; ii < 2; ii++) {
				for (int jj = 0; jj < 2; jj++) {
					corners[ii][jj] = std::max(corners[ii][jj], c - mid + d[ord[0][i]] + (hwb[jj] == ord[0][i] ? hsbb[jj] : hbb[jj]) + (ii ? -pre[ord[0][i]] : pre[ord[0][i]]));
				}
			}
		} else {
			while (~rb && her[0][i] + her[1][rb] > mid) {
				for (int k = 0; k < 2; k++) {
					hbb[k] = std::max(hbb[k], (long long) d[ord[1][rb]] + (k ? -pre[ord[1][rb]] : pre[ord[1][rb]]));
				}
				rb--;
			}
			for (int ii = 0; ii < 2; ii++) {
				for (int jj = 0; jj < 2; jj++) {
					corners[ii][jj] = std::max(corners[ii][jj], c - mid + d[ord[0][i]] + hbb[jj] + (ii ? -pre[ord[0][i]] : pre[ord[0][i]]));
				}
			}
		}
		if (corners[0][0] + corners[1][1] > 0LL || corners[0][1] + corners[1][0] > 0LL) {
			return false;
		}
	}
	for (int i = 0; i < n; i++) {
		long long l = std::max(+corners[0][0] - pre[i], +corners[1][0] + pre[i]);
		long long r = std::min(-corners[0][1] + pre[i], -corners[1][1] - pre[i]);
		if (l > r) {
			continue;
		}
		auto lb = std::lower_bound(pre, pre + n, l);
		if (lb != pre + n && *lb <= r) {
			return true;
		}
	}
	return false;
}

long long find_shortcut(int _n, std::vector <int> el, std::vector <int> d, int _c) {
	n = _n;
	c = _c;
	if (n == 2) {
		return (long long) std::min(el[0], c) + d[0] + d[1];
	}
	for (int i = 1; i < n; i++) {
		pre[i] = pre[i - 1] + el[i - 1];
	}
	for (int i = 0; i < n; i++) {
		her[0][i] = +pre[i] + d[i];
		her[1][i] = -pre[i] + d[i];
	}
	for (int i = 0; i < 2; i++) {
		std::iota(ord[i], ord[i] + n, 0);
		std::sort(ord[i], ord[i] + n, [&] (int u, int v) -> bool { return her[i][u] < her[i][v]; });
		std::sort(her[i], her[i] + n);
	}
	long long l = 0, r = pre[n - 1] + (1LL << 31);
	while (l <= r) {
		long long mid = (l + r) >> 1;
		if (check(mid, d)) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3