oj.uz

Submission #612890

# Submission time Handle Problem Language Result Execution time Memory
612890 2022-07-30T01:59:13 Z Temmie Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>

constexpr const int mxn = 1'000'000;

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

bool check(long long mid) {
	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];
	}
	memcpy(d, _d.data(), sizeof(int) * n);
	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)) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 4, 80 is a correct answer
2 Correct 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 1 ms 384 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 1
6 Halted 0 ms 0 KB -