#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <immintrin.h> #ifndef DEBUG //#pragma GCC optimize("O3") //#pragma GCC target("avx2") #endif using namespace __gnu_pbds; using namespace __gnu_cxx; using namespace std; // using ld = long double; using ll = long long; using i128 = __int128; using ull = unsigned long long; using pll = std::pair<ll, ll>; using cmpl = std::complex<ld>; template<typename T> using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>; constexpr ll MOD1 = 998244353; constexpr ll MOD = 1000000007; constexpr ll INV2 = 499122177; constexpr ld PI = 3.141592653589793; const ld eps = 1e-7; const ll K = 3; //const ll C = 200; std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count()); ld START_TIME = clock(); ll n, m, min1, max1; std::vector<std::vector<ll>> a; bool check(ll mid){ std::vector<ll> mxn(m, 0); mxn[0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == min1){ mxn[j] = i + 1; } } } ll sufmn = 0; for (int i = m - 1; i >= 0; --i) { sufmn = std::max(sufmn, mxn[i]); mxn[i] = sufmn; } ll mxdd = n; for (int i = 0; i < m; ++i) { while (mxn[i] < mxdd && a[mxn[i]][i] - min1 <= mid){ ++mxn[i]; } mxdd = mxn[i]; } ll mxdf = 0, mxdf1 = 0; for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { if (i < mxn[j]){ mxdf = std::max(mxdf, a[i][j] - min1); } else{ mxdf = std::max(mxdf, max1 - a[i][j]); } } } mxn.assign(m, 0); mxn[0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == max1){ mxn[j] = i + 1; } } } sufmn = 0; for (int i = m - 1; i >= 0; --i) { sufmn = std::max(sufmn, mxn[i]); mxn[i] = sufmn; } mxdd = n; for (int i = 0; i < m; ++i) { while (mxn[i] < mxdd && max1 - a[mxn[i]][i] <= mid){ ++mxn[i]; } mxdd = mxn[i]; } for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { if (i >= mxn[j]){ mxdf1 = std::max(mxdf1, a[i][j] - min1); } else{ mxdf1 = std::max(mxdf1, max1 - a[i][j]); } } } return mxdf <= mid || mxdf1 <= mid; } bool check1(ll mid){ std::vector<ll> mxn(m, 0); mxn[0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == min1){ mxn[j] = i + 1; } } } ll sufmn = 0; for (int i = 0; i < m; ++i) { sufmn = std::max(sufmn, mxn[i]); mxn[i] = sufmn; } ll mxdd = n; for (int i = m - 1; i >= 0; --i) { while (mxn[i] < mxdd && a[mxn[i]][i] - min1 <= mid){ ++mxn[i]; } mxdd = mxn[i]; } ll mxdf = 0, mxdf1 = 0; for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { if (i < mxn[j]){ mxdf = std::max(mxdf, a[i][j] - min1); } else{ mxdf = std::max(mxdf, max1 - a[i][j]); } } } mxn.assign(m, 0); mxn[0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == max1){ mxn[j] = i + 1; } } } sufmn = 0; for (int i = 0; i < m; ++i) { sufmn = std::max(sufmn, mxn[i]); mxn[i] = sufmn; } mxdd = n; for (int i = m - 1; i >= 0; --i) { while (mxn[i] < mxdd && max1 - a[mxn[i]][i] <= mid){ ++mxn[i]; } mxdd = mxn[i]; } for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { if (i >= mxn[j]){ mxdf1 = std::max(mxdf1, a[i][j] - min1); } else{ mxdf1 = std::max(mxdf1, max1 - a[i][j]); } } } return mxdf <= mid || mxdf1 <= mid; } void solve(){ std::cin >> n >> m; a.resize(n, std::vector<ll>(m)); min1 = 1e18; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { std::cin >> a[i][j]; } min1 = std::min(min1, *std::min_element(a[i].begin(), a[i].end())); max1 = std::max(max1, *std::max_element(a[i].begin(), a[i].end())); } if (min1 == max1){ std::cout << 0; return; } ll l = 0, r = max1 - min1; while (r - l > 1){ ll mid = (l + r) / 2; if (check(mid) || check1(mid)){ r = mid; } else{ l = mid; } } std::cout << r; } signed main() { #ifdef DEBUG std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin); #else // std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout); #endif std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false); int tt = 1; // std::cin >> tt; while (tt--) { solve(); } #ifdef DEBUG std::cerr << '\n'; ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC; std::cerr << "Time: " << TIME << '\n'; #endif }