Submission #1173216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173216		AmirAli_H1	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	30 / 100	5069 ms	31120 KiB

Main

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 20) + 7;
const int oo = 1e9 + 4;

int n, m; pll A[maxn];
ll A1[maxn], A2[maxn];
int arr[maxn]; pii val1[maxn], val2[maxn];
int M1[maxn], M2[maxn];
vector<pii> vc, lsx;

bool cmp(int i, int j) {
	return (A[i] < A[j]);
}

void add1(int l, int r, int i) {
	vc.clear();
	if (i - m + 1 >= 0) vc.pb(Mp(i - m + 1, i + 1));
	else {
		vc.pb(Mp(0, i + 1)); vc.pb(Mp(n + (i - m + 1), n));
	}
	for (auto f : vc) {
		int lx = max(f.F, l), rx = min(f.S, r);
		if (lx >= rx) continue;
		M1[lx]++; M1[rx]--;
	}
}

void add2(int l, int r, int i) {
	vc.clear();
	if (i - m + 1 >= 0) vc.pb(Mp(i - m + 1, i + 1));
	else {
		vc.pb(Mp(0, i + 1)); vc.pb(Mp(n + (i - m + 1), n));
	}
	for (auto f : vc) {
		int lx = max(f.F, l), rx = min(f.S, r);
		if (lx >= rx) continue;
		M2[lx]++; M2[rx]--;
	}
}

void getx(int x1, int x2, int l, int r) {
	int valx = x1;
	vc.clear(); lsx.clear();
	if (l > r) return ;

	int f1 = min(x1, x2), f2 = max(x1, x2) - min(x1, x2), f3 = (m - 1) - max(x1, x2);
	if (valx >= l && valx <= r) {
		vc.pb(Mp(0, 1));
	}
	int lx = max(l, valx - f1), rx = min(r, valx - 1);
	if (lx <= rx) {
		vc.pb(Mp(valx - rx, valx - lx + 1));
	}
	valx -= f1;
	if (valx >= l && valx <= r) {
		vc.pb(Mp(f1 + 1, f1 + f2 + 1));
	}
	lx = max(l, valx + 1), rx = min(r, valx + f3);
	if (lx <= rx) {
		vc.pb(Mp(f1 + f2 + lx - valx, f1 + f2 + rx - valx + 1));
	}

	int j = 0;
	for (auto f : vc) {
		if (j < f.F) lsx.pb(Mp(j, f.F));
		j = f.S;
	}
	if (j < m) lsx.pb(Mp(j, m));
}

bool check(int x) {
	for (int i = 0; i < n; i++) {
		int j1 = lower_bound(A1, A1 + m, A[i].F - x) - A1;
		int j2 = upper_bound(A1, A1 + m, A[i].F + x) - A1 - 1;
		val1[i] = Mp(j1, j2);
		j1 = lower_bound(A2, A2 + m, A[i].F - x) - A2;
		j2 = upper_bound(A2, A2 + m, A[i].F + x) - A2 - 1;
		val2[i] = Mp(j1, j2);
		if (val1[i].F > val1[i].S && val2[i].F > val2[i].S) return 0;
	}
	fill(M1, M1 + n, 0); fill(M2, M2 + n, 0);

	int r1 = -1, r2 = -1;
	for (int j = 0; j < n; j++) {
		int i = arr[j];
		int mx = min(m, j), mn = m - min(m, n - j);
		if (val1[i].F > val1[i].S || val1[i].F > mx || val1[i].S < mn) add1(0, n, i);
		else if (i != 0 && i != m) {
			getx(r1 + 1, m - r2, val1[i].F, val1[i].S);
			for (auto f : lsx) add1(f.F, f.S, i);
			getx(m - r2, r1 + 1, m - val1[i].S, m - val1[i].F);
			for (auto f : lsx) add1(m + f.F, m + f.S, i);
		}

		if (val2[i].F > val2[i].S || val2[i].F > mx || val2[i].S < mn) add2(0, n, i);
		else if (i != 0 && i != m) {
			getx(r1 + 1, m - r2, val2[i].F, val2[i].S);
			for (auto f : lsx) add2(f.F, f.S, i);
			getx(m - r2, r1 + 1, m - val2[i].S, m - val2[i].F);
			for (auto f : lsx) add2(m + f.F, m + f.S, i);
		}

		if (i == 0 || i == m) r1 = r2 = i;
		else if (i < m) r1 = i;
		else r2 = (n - i);
	}

	for (int i = 1; i < n; i++) {
		M1[i] += M1[i - 1]; M2[i] += M2[i - 1];
	}
	for (int i = 0; i < n; i++) {
		int j = (i + m) % n;
		if (M1[i] == 0 && M2[j] == 0) return 1;
	}
	return 0;
}

void solve() {
	cin >> m; n = 2 * m;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F; A[i].S = (2 * min(i, n - i)) + (i / m);
	}
	for (int i = 0; i < m; i++) cin >> A1[i];
	for (int i = 0; i < m; i++) cin >> A2[i];
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	sort(A1, A1 + m); sort(A2, A2 + m);
	
	int l = -1, r = oo;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	cout << r << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int T = 1;
	while (T--) {
		solve();
	}
	
	return 0;
}

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