Submission #25183164

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template <class T> struct SparseTable {
	std::vector<T> v;
	std::vector<std::vector<int>> jump;
	int type = 1;

	int level(int x) { return 31 - __builtin_clz(x); }

	int comb(int a, int b) {
		return v[a] == v[b] ? std::min(a, b) : (type * v[a] < type * v[b] ? a : b);
	}

	void init(const std::vector<T>& _v) {
		v = _v;
		jump = {std::vector<int>((int)v.size())};
		iota(jump[0].begin(), jump[0].end(), 0);
		for (int j = 1; (1 << j) <= (int)v.size(); j++) {
			jump.push_back(std::vector<int>((int)v.size() - (1 << j) + 1));
			for (int i = 0; i < (int)jump[j].size(); i++) {
				jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int index(int l, int r) {
		assert(l <= r);
		int d = level(r - l + 1);
		return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
	}

	T query(int l, int r) {
		return v[index(l, r)];
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	
	long long INF = 1e18;
	int n;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<long long> tmp;
	SparseTable<long long> mnst, mxst;
	mxst.type = -1;
	mnst.init(a);
	mxst.init(a);
	long long ans = mxst.query(0, n - 1) - mnst.query(0, n - 1);
	vector<vector<array<long long, 2>>> st(n, vector<array<long long, 2>>(n, {-INF, INF}));
	for (int c = 0; c < n - 1; ++c) {
		for (int l = c; l >= 0; --l) {
			int r = c - l + c + 1;
			if (r >= n) {
				break;
			}
			st[l][r] = st[l + 1][r - 1];
			st[l][r][0] = max(st[l][r][0], a[l] + a[r]);
			st[l][r][1] = min(st[l][r][1], a[l] + a[r]);
		}
	}
	for (int len = 0; len <= n / 2; ++len) {
		long long mx = -INF;
		long long mn = INF;
		for (int i = 0; i < len; ++i) {
			long long v = a[i] + a[n - 1 - i];
			mx = max(mx, v);
			mn = min(mn, v);
		}
		for (int i = len + 1; i <= n - 1 - len; i += 2) {
			long long lo = mn;
			long long hi = mx;
			int l = i + 1;
			int r = n - 1 - len;
			if (l <= r) {
				lo = min(lo, mnst.query(l, r));
				hi = max(hi, mxst.query(l, r));
			}
			lo = min(lo, st[len][i][1]);
			hi = max(hi, st[len][i][0]);
			ans = min(ans, hi - lo);
		}
		for (int i = n - 1 - len - 1; i >= len; i -= 2) {
			long long lo = mn;
			long long hi = mx;
			int l = len;
			int r = i - 1;
			if (l <= r) {
				lo = min(lo, mnst.query(l, r));
				hi = max(hi, mxst.query(l, r));
			}
			lo = min(lo, st[i][n - 1 - len][1]);
			hi = max(hi, st[i][n - 1 - len][0]);
			ans = min(ans, hi - lo);
		}
		if (len <= n - 1 - len) {
			mx = max(mx, mxst.query(len, n - 1 - len));
			mn = min(mn, mnst.query(len, n - 1 - len));
		}
		ans = min(ans, mx - mn);
	}
	cout << ans << '\n';
	return 0;
}

/**
 * [l, r]
 * pairing must be opposite
 * a <= b <= c <= d
 * a, c, single
 * a, c, b + d
 * a + d, b + c
 */ 

Submission Info

Judge Result