Submission #1229509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229509		lohacho	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	2769 ms	47420 KiB

Main

#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...)
#define debugArr(...)
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())
#define comp(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define lb(v, x) (lower_bound(all(v), x) - v.begin())
#define MAX(x, y) (x = max(x, y))
#define MIN(x, y) (x = min(x, y))
#define pb push_back
#define pi array<int, 2>
using namespace std;

#define int long long

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;
	vector<int> a(n * 2), b(n), c(n);
	for(int i = 0; i < n * 2; ++i) cin >> a[i];
	for(int i = 0; i < n; ++i) cin >> b[i];
	for(int i = 0; i < n; ++i) cin >> c[i];

	sort(all(b)), sort(all(c));

	auto ra = a, rb = b, rc = c;
	for(int i = 0; i < n; ++i) swap(ra[i], ra[n + i]);
	reverse(all(rb));
	reverse(all(rc));
	for(auto &v : ra) v = -v;
	for(auto &v : rb) v = -v;
	for(auto &v : rc) v = -v;

	int low = 0, high = (int)1e9, mid;
	while(low < high){
		mid = low + high >> 1;

		auto sol = [&](vector<int> x, vector<int> y){
			vector<pi> lr(n * 2);
			for(int i = 0, j = 0; i <= n; ++i){
				while(j < n && x[i] - y[j] > mid) ++j;
				lr[i][0] = j;
			}
			for(int i = n, j = n - 1; i >= 0; --i){
				while(j >= 0 && y[j] - x[i] > mid) --j;
				lr[i][1] = j;
			}

			for(int i = n * 2 - 1, j = 0; i > n; --i){
				while(j < n && x[i] - y[j] > mid) ++j;
				lr[i][0] = j;
			}
			for(int i = n + 1, j = n - 1; i < n * 2; ++i){
				while(j >= 0 && y[j] - x[i] > mid) --j;
				lr[i][1] = j;
			}

			vector<int> rb(n * 2);
			for(int i = 0, j = n * 2 - 1; i < n; ++i){
				while(x[j] < x[i]) --j;
				rb[i] = j;
			}
			for(int i = n * 2 - 1, j = 1; i > n; --i){
				while(j < n && x[j] <= x[i]) ++j;
				rb[i] = j;
			}

			vector<int> add(n + 1);
			auto push = [&](int l, int r, int p){
				MAX(l, 0ll);
				MIN(r, n - 1);
				MAX(l, p - n + 1);
				MIN(r, p);
				if(l > r) return;
				add[l] += 1;
				add[r + 1] -= 1;
			};
			for(int i = 0; i < n; ++i){
				int dec = min(i, rb[i] - n + 1);

				if(0 <= dec){
					push(i - lr[i][1], min(dec, i - lr[i][0]), i);
				}
				if(dec < i && lr[i][0] <= i - dec && i - dec <= lr[i][1]){
					push(dec + 1, i, i);
				}
			}
			if(lr[n][0] <= n - 1 && n - 1 <= lr[n][1]){
				push(1, n - 1, n);
			}
			for(int i = n * 2 - 1; i > n; --i){
				int dec = max(i - n + 1, rb[i]);
				int diff = n - dec;

				if(dec <= n - 1){
					push(max(dec, lr[i][0] - n + i + 1), lr[i][1] - n + i + 1, i);
				}
				if(i - n + 1 < dec && lr[i][0] <= n * 2 - i - 1 - (n - dec) && n * 2 - i - 1 - (n - dec) <= lr[i][1]){
					push(i - n + 1, dec - 1, i);
				}
			}

			vector<int> rv(n);
			for(int i = 0; i < n; ++i){
				add[i + 1] += add[i];
				if(add[i] == n) rv[i] = 1;
			}

			return rv;
		};

		int ok = 0;
		for(int r = 0; r < 2; ++r){
			auto o = sol(a, b);
			auto t = sol(ra, rc);

			for(int i = 0; i < n; ++i){
				if(o[i] && t[i]){
					ok = 1;
					break;
				}
			}

			swap(b, c);
			swap(rb, rc);
		}

		if(ok){
			high = mid;
		}
		else{
			low = mid + 1;
		}
	}

	cout << low;

	return 0;
}

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