Submission #1173436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173436		Troll321	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	304 ms	18116 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], posIn[MAXN];
ll occur[MAXN];
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) {
		offIn[i] = lower_bound(R.begin(), R.end(), val[i]) - R.begin();
		offIn[i] = n-offIn[i];
	}

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

		occur[val[i]]++;
	}
}

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";
			}
		} else {
			// In
			if(abs(val[i]-arra[ntot-i+1]) <= x) {
				l = i-n+1;
				r = n+1;
				diff[l]++;
				diff[r]--;
				// cout << l << " " << r << " <> ";
			}

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

	// ------
	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: 0 / 37
• Subtask 5: 0 / 33