Submission #1269864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269864		MateiKing80	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	37 / 100	499 ms	9828 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 300005;
int mic[N], mare[N], a[N], b[N], n;
pii lra[N], lrb[N];


bool fct(int k) {
	int cst = 0, cdr = -1;
	for (int i = 0; i < n; i ++) {
		while (cst < n && mic[cst] < a[i] - k)
			cst ++;
		while (cdr < n - 1 && mic[cdr + 1] <= a[i] + k)
			cdr ++;
		lra[i] = {cst, cdr};
	}
	cst = 0, cdr = -1;
	for (int i = 0; i < n; i ++) {
		while (cst < n && mare[cst] < b[i] - k)
			cst ++;
		while (cdr < n - 1 && mare[cdr + 1] <= b[i] + k)
			cdr ++;
		lrb[i] = {cst, cdr};
	}
	int mx = n;
	for (int i = 0; i < n; i ++) {
		if (abs(mic[i] - b[i]) > k || abs(mare[n - i - 1] - a[n - i - 1]) > k) {
			mx = i;
			break;
		}
	}
	if (mx == n)
		return true;
	int m = n, M = 0;
	for (int i = n - 1; i >= 0; i --) {
		m = min(m, min(lra[n - i - 1].sc - n + i + 1, i - lrb[i].fr));
		M = max(M, max(lra[n - i - 1].fr - n + i + 1, i - lrb[i].sc));
		if (M <= i && i <= m && i <= mx)
			return true;
	}
	return false;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i ++)
		cin >> mic[i];
	for (int i = n - 1; i >= 0; i --)
		cin >> mare[i];
	for (int i = 0; i < n; i ++)
		cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i ++)
		cin >> b[i];
	sort(b, b + n);
	
	int pos1 = -1;
	for (int pas = 1 << 30; pas; pas >>= 1)
		if (!fct(pos1 + pas))
			pos1 += pas;
	swap(a, b);
	int pos2 = -1;
	for (int pas = 1 << 30; pas; pas >>= 1)
		if (!fct(pos2 + pas))
			pos2 += pas;
	cout << min(pos1, pos2) + 1 << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 37 / 37
• Subtask 5: 0 / 33