Submission #1173547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173547		Troll321	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	37 / 100	3724 ms	28756 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 6e5 + 5; 
const ll MAX = 1e18;
const ll MAXBINSER = 1e9;

ll n, ntot, ans = MAX, val[MAXN], red[MAXN], blue[MAXN];

ll offIn[MAXN], offOut[MAXN], posOut[MAXN], posIn[MAXN];
unordered_map<ll,ll> occur;
void precomp() {
	vector<ll> L, R;
	for (int i = 1; i <= n; ++i) {
		L.push_back(val[i]);
	}
	for (int i = ntot; i >= n+1; --i) {
		R.push_back(val[i]);
	}

	for (int i = 1; i <= n; ++i) {
		// Leftmost yang >= val
		offIn[i] = lower_bound(R.begin(), R.end(), val[i]) - R.begin();
		offIn[i] = n-offIn[i];

		posOut[i] = lower_bound(R.begin(), R.end()-i+1, val[i]) - R.begin();
		posOut[i] = i+posOut[i];
		offOut[i] = i+n-posOut[i];

		// cout << i << " | " << posOut[i] << " " << offOut[i] << "|\n";
	}

	for (int i = n+1; i <= ntot; ++i) {
		posIn[i] = upper_bound(L.begin()+(i-n-1), L.end(), val[i]) - (L.begin()+(i-n-1));
		// Never Zero due to Constrain
		offIn[i] = i-n-1+posIn[i];
		// cout << i << " | " << offIn[i] << " " << posIn[i] << "||\n";
		// cout << offIn[i] << " " << posIn[i] << "|\n";

		// occur[val[i]]++;

		// Rightmost yang <= val
		offOut[i] = upper_bound(L.begin(), L.end(), val[i]) - L.begin();
		offOut[i] = offOut[i]+1;
	}
}

ll diff[MAXN];
bool solve(ll x, ll arra[], ll arrb[]) {
	memset(diff, 0, sizeof(diff));

	for (ll i = 1; i <= ntot; ++i) {
		// Search Range For val[i]
		ll idl = lower_bound(arra+1, arra+1+n, val[i]-x) - arra;
		ll idr = upper_bound(arra+1, arra+1+n, val[i]+x) - arra;
		if(idl > n || idr == 1 || idl >= idr) {
			idl = -1;
			idr = 0;
		}
		idr--;

		ll idl2 = lower_bound(arrb+1, arrb+1+n, val[i]-x) - arrb;
		ll idr2 = upper_bound(arrb+1, arrb+1+n, val[i]+x) - arrb;
		if(idl2 > n || idr2 == 1 || idl2 >= idr2) {
			idl2 = -1;
			idr2 = 0;
		}
		idr2--;

		// cout << i << " " << x << "| [" << idl << "," << idr << "] [" << idl2 << "," << idr2 << "]\n";

		ll l, r;
		if (i <= n) {
			// In
			if(idl != -1) {
				l = max((ll)1, i+1-idr);
				r = min(offIn[i], i+1-idl)+1;
				diff[l]++;
				diff[r]--;
				// cout << l << " " << r << " <> ";

				if(i+1-idl > offIn[i] && abs(val[i] - arra[i+1-offIn[i]]) <= x) {
					l = offIn[i]+1;
					r = i+1;
					diff[l]++;
					diff[r]--;
				}
			}


			// Out
			// if(abs(val[i]-arrb[i]) <= x) {
			// 	l = i+1;
			// 	r = n+1;
			// 	diff[l]++;
			// 	diff[r]--;
			// 	// cout << l << " " << r << "|\n";
			// }
			// --\
			// l <= offOut[i]
			if(offOut[i] >= i+1 && abs(val[i]-arrb[posOut[i]]) <= x) {
				l = i+1;
				r = offOut[i]+1;
				diff[l]++;
				diff[r]--;
			}
			// l > offOut[i]
			if(offOut[i] < n && idl2 != -1) {
				l = max(posOut[i]+1, offOut[i]+posOut[i]-idr2);
				r = min(n, offOut[i]+posOut[i]-idl2)+1;
				diff[l]++;
				diff[r]--;
			}
		} else {
			// In
			// __/
			// l <= offIn[i]
			if(offIn[i] >= i-n+1 && abs(val[i]-arra[posIn[i]]) <= x) {
				l = i-n+1;
				r = offIn[i]+1;
				diff[l]++;
				diff[r]--;
			}
			// l > offIn[i]
			if(offIn[i] < n && idl != -1) {
				l = max(posIn[i]+1, idl+offIn[i]-posIn[i]);
				r = min(n, idr+offIn[i]-posIn[i])+1;
				diff[l]++;
				diff[r]--;
			}

			// Out
			if(idl2 != -1) {
				l = max((ll)1, idl2+i-ntot);
				r = min(offOut[i], idr2+i-ntot)+1;
				diff[l]++;
				diff[r]--;
				// cout << l << " " << r << "|\n";

				if (idr2+i-ntot > offOut[i] && abs(val[i] - arrb[offOut[i]+i-ntot]) <= x) {
					l = offOut[i]+1;
					r = i-n+1;
					diff[l]++;
					diff[r]--;
				}
			}
		}
	}

	// ------
	ll cur = 0;
	for (int i = 1; i <= ntot; ++i) {
		cur += diff[i];
		if(cur == ntot) {return true;}
	}
	return false;
}

int main() {
	cin >> n;
	ntot = 2*n;

	for (int i = 1; i <= ntot; ++i) {
		cin >> val[i];
	}

	for (int i = 1; i <= n; ++i) {
		cin >> red[i];
	}

	for (int i = 1; i <= n; ++i) {
		cin >> blue[i];
	}

	sort(red+1, red+1+n);
	sort(blue+1, blue+1+n);

	precomp();

	// for (int i = 1; i <= n; ++i) {
	// 	cout << red[i] << " ";
	// } cout << "|\n";
	// for (int i = 1; i <= n; ++i) {
	// 	cout << blue[i] << " ";
	// } cout << "|\n";

	ll l = 0, r = MAXBINSER;
	while(l <= r) {
		ll mid = (l+r) >> 1;
		// cout << "---------" << mid << "--------\n";
		if(solve(mid, red, blue) || solve(mid, blue, red)) {
			ans = mid;
			r = mid-1;
		} else {
			l = mid+1;
		}
	}
	cout << ans << "\n";
	return 0;
}

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