Submission #1173170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173170		AmirAli_H1	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	30 / 100	268 ms	66280 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;

struct node {
	int lazy; pii min, max;	
};

int n, m; pll A[maxn];
ll A1[maxn], A2[maxn];
int arr[maxn]; pii val1[maxn], val2[maxn];
node t[2 * maxn], null, f; int cnt, M[maxn];
vector<ll> lsx;

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

node fx(node a, node b, int lazy) {
	node res; res.lazy = 0;
	res.min = min(a.min, b.min); res.max = max(a.max, b.max);
	res.lazy += lazy; res.min.F += lazy; res.max.F += lazy;
	return res;
}

void build(int v, int tl, int tr, bool R) {
	t[v].lazy = 0;
	if (tr - tl == 1) {
		int j = tl;
		if (R == 1) j = (j + m);
		if (j >= n) j -= n;
		if (!M[j]) t[v] = null;
		else {
			t[v].min = Mp(0, tl); t[v].max = Mp(0, tl);
		}
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid, R); build(2 * v + 2, mid, tr, R);
	t[v] = fx(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void del_val(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] = null;
		return ;
	}
	int mid = (tl + tr) / 2;
	if (i < mid) del_val(2 * v + 1, tl, mid, i);
	else del_val(2 * v + 2, mid, tr, i);
	t[v] = fx(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void add_val(int v, int tl, int tr, int l, int r, int x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl || l >= r) return ;
	if (l == tl && r == tr) {
		t[v].lazy += x; t[v].min.F += x; t[v].max.F += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v] = fx(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

node get_val(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl || l >= r) return null;
	if (l == tl && r == tr) return t[v];
	int mid = (tl + tr) / 2;
	return fx(get_val(2 * v + 1, tl, mid, l, r), get_val(2 * v + 2, mid, tr, l, r), t[v].lazy);
}

void addx(int l, int r) {
	add_val(0, 0, n, l, r, 1);
	add_val(0, 0, n, l + n, n, 1);
}

node getx(int l, int r) {
	return fx(get_val(0, 0, n, l, r), get_val(0, 0, n, l + n, n), 0);
}

void delx(int j, int R) {
	del_val(0, 0, n, j);
	if (R == 1) j = (j + m);
	if (j >= n) j -= n;
	cnt -= M[j]; M[j] = 0;
}

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;
	}
	cnt = n; fill(M, M + n, 1);

	if (n <= 4000) {
		build(0, 0, n, 0);
		for (int j = 0; j < n; j++) {
			int i = arr[j];
			f = getx(i - m + 1, i + 1);
			while (f.min.F < val1[i].F) {
				int j = f.min.S; delx(j, 0);
				if (cnt <= 0) return 0;
				f = getx(i - m + 1, i + 1);
			}
			while (f.max.F > val1[i].S) {
				int j = f.max.S; delx(j, 0);
				if (cnt <= 0) return 0;
				f = getx(i - m + 1, i + 1);
			}
			addx(i - m + 1, i + 1);
		}
		build(0, 0, n, 1);
		for (int j = 0; j < n; j++) {
			int i = arr[j];
			f = getx(i - m + 1, i + 1);
			while (f.min.F < val2[i].F) {
				int j = f.min.S; delx(j, 1);
				if (cnt <= 0) return 0;
				f = getx(i - m + 1, i + 1);
			}
			while (f.max.F > val2[i].S) {
				int j = f.max.S; delx(j, 1);
				if (cnt <= 0) return 0;
				f = getx(i - m + 1, i + 1);
			}
			addx(i - m + 1, i + 1);
		}
	}
	return 1;
}

int cal(int i) {
	ll mx = 0;
	lsx.clear();
	for (int j = i; j < i + n; j++) {
		int R = j;
		if (R >= 2 * n) R -= 2 * n;
		lsx.pb(A[R].F);
	}
	sort(all(lsx));
	for (int i = 0; i < n; i++) mx = max(mx, abs(A1[i] - lsx[i]));
	lsx.clear();
	for (int j = i + n; j < i + (2 * n); j++) {
		int R = j;
		if (R >= 2 * n) R -= 2 * n;
		lsx.pb(A[R].F);
	}
	sort(all(lsx));
	for (int j = 0; j < n; j++) mx = max(mx, abs(A2[j] - lsx[j]));
	return mx;
}

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 = cal(rng() % n);
	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);
	
	null.min = Mp(oo, -1); null.max = Mp(-oo, -1);

	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