#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair <int, int> pii;
const int MAXN = 2e3 + 5, INF = 1e9 + 5;
int n, m, k;
int a[MAXN][MAXN];
pii mx {1, 1}, mn {1, 1};
int pmx[2][MAXN][MAXN], smx[2][MAXN][MAXN], pmn[2][MAXN][MAXN], smn[2][MAXN][MAXN];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
if(a[i][j] > a[mx.F][mx.S]) mx = {i, j};
if(a[i][j] < a[mn.F][mn.S]) mn = {i, j};
}
}
for(int i = 1; i <= n; ++i) {
pmn[0][i][0] = INF;
smn[0][i][m + 1] = INF;
for(int j = 1; j <= m; ++j) {
pmx[0][i][j] = max(pmx[0][i][j - 1], a[i][j]);
pmn[0][i][j] = min(pmn[0][i][j - 1], a[i][j]);
}
for(int j = m; j >= 1; --j) {
smx[0][i][j] = max(smx[0][i][j + 1], a[i][j]);
smn[0][i][j] = min(smn[0][i][j + 1], a[i][j]);
}
}
for(int j = 1; j <= m; ++j) {
pmn[1][0][j] = INF;
smn[1][n + 1][j] = INF;
for(int i = 1; i <= n; ++i) {
pmx[1][i][j] = max(pmx[1][i - 1][j], a[i][j]);
pmn[1][i][j] = min(pmn[1][i - 1][j], a[i][j]);
}
for(int i = n; i >= 1; --i) {
smx[1][i][j] = max(smx[1][i + 1][j], a[i][j]);
smn[1][i][j] = min(smn[1][i + 1][j], a[i][j]);
}
}
auto check = [](int x) -> bool {
{ // fix mn
int up = a[mn.F][mn.S] + x;
{ // left side
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int l = 1, r = m, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(pmx[0][i][mid] <= up) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
{ // right side
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int l = 1, r = m, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(smx[0][i][mid] <= up) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
{ // top side
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int l = 1, r = n, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(pmx[1][mid][j] <= up) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
{ // bottom side
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int l = 1, r = n, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(smx[1][mid][j] <= up) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, pmx[1][res - 1][j]);
mnn = min(mnn, pmn[1][res - 1][j]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // fix mx
int lo = a[mx.F][mx.S] - x;
{ // left side
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int l = 1, r = m, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(pmn[0][i][mid] >= lo) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
{ // right side
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int l = 1, r = m, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(smn[0][i][mid] >= lo) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
{ // top side
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int l = 1, r = n, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(pmn[1][mid][j] >= lo) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
{ // bottom side
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int l = 1, r = n, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(smn[1][mid][j] >= lo) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(res == -1) {
mxx = INF;
mnn = -INF;
break;
}
mxx = max(mxx, pmx[1][res - 1][j]);
mnn = min(mnn, pmn[1][res - 1][j]);
}
if(mxx - mnn <= x) return 1;
}
}
return 0;
};
int l = 0, r = 1e9, ans = 1e9;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
