#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
vt <int> rec(n + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[i] = res;
}
if(flag) { // increasing
int last = INF;
int mxx = 0, mnn = INF;
for(int i = n; i >= 1; --i) {
int res = min(rec[i], last);
last = res;
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = INF;
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int res = min(rec[i], last);
last = res;
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // right side
vt <int> rec(n + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[i] = res;
}
if(flag) { // increasing
int last = 0;
int mxx = 0, mnn = INF;
for(int i = n; i >= 1; --i) {
int res = max(rec[i], last);
last = res;
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = 0;
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int res = max(rec[i], last);
last = res;
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // top side
vt <int> rec(m + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[j] = res;
}
if(flag) { // increasing
int last = INF;
int mxx = 0, mnn = INF;
for(int j = m; j >= 1; --j) {
int res = min(rec[j], last);
last = res;
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = INF;
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int res = min(rec[j], last);
last = res;
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // bottom side
vt <int> rec(m + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[j] = res;
}
if(flag) { // increasing
int last = 0;
int mxx = 0, mnn = INF;
for(int j = m; j >= 1; --j) {
int res = max(rec[j], last);
last = res;
mxx = max(mxx, pmx[1][res - 1][j]);
mnn = min(mnn, pmn[1][res - 1][j]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = 0;
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int res = max(rec[j], last);
last = res;
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
vt <int> rec(n + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[i] = res;
}
if(flag) { // increasing
int last = INF;
int mxx = 0, mnn = INF;
for(int i = n; i >= 1; --i) {
int res = min(rec[i], last);
last = res;
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = INF;
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int res = min(rec[i], last);
last = res;
mxx = max(mxx, smx[0][i][res + 1]);
mnn = min(mnn, smn[0][i][res + 1]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // right side
vt <int> rec(n + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[i] = res;
}
if(flag) { // increasing
int last = 0;
int mxx = 0, mnn = INF;
for(int i = n; i >= 1; --i) {
int res = max(rec[i], last);
last = res;
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = 0;
int mxx = 0, mnn = INF;
for(int i = 1; i <= n; ++i) {
int res = max(rec[i], last);
last = res;
mxx = max(mxx, pmx[0][i][res - 1]);
mnn = min(mnn, pmn[0][i][res - 1]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // top side
vt <int> rec(m + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[j] = res;
}
if(flag) { // increasing
int last = INF;
int mxx = 0, mnn = INF;
for(int j = m; j >= 1; --j) {
int res = min(rec[j], last);
last = res;
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = INF;
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int res = min(rec[j], last);
last = res;
mxx = max(mxx, smx[1][res + 1][j]);
mnn = min(mnn, smn[1][res + 1][j]);
}
if(mxx - mnn <= x) return 1;
}
}
{ // bottom side
vt <int> rec(m + 1, 0);
bool flag = 1;
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) {
flag = 0;
break;
}
rec[j] = res;
}
if(flag) { // increasing
int last = 0;
int mxx = 0, mnn = INF;
for(int j = m; j >= 1; --j) {
int res = max(rec[j], last);
last = res;
mxx = max(mxx, pmx[1][res - 1][j]);
mnn = min(mnn, pmn[1][res - 1][j]);
}
if(mxx - mnn <= x) return 1;
}
if(flag) { // decreasing
int last = 0;
int mxx = 0, mnn = INF;
for(int j = 1; j <= m; ++j) {
int res = max(rec[j], last);
last = res;
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 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
720 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
1 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
720 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
1 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
2 ms |
860 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9052 KB |
Output is correct |
| 17 |
Correct |
9 ms |
9172 KB |
Output is correct |
| 18 |
Correct |
6 ms |
10328 KB |
Output is correct |
| 19 |
Correct |
10 ms |
10308 KB |
Output is correct |
| 20 |
Correct |
6 ms |
9564 KB |
Output is correct |
| 21 |
Correct |
8 ms |
10588 KB |
Output is correct |
| 22 |
Correct |
9 ms |
10328 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9308 KB |
Output is correct |
| 24 |
Correct |
7 ms |
8332 KB |
Output is correct |
| 25 |
Correct |
7 ms |
9304 KB |
Output is correct |
| 26 |
Correct |
7 ms |
10564 KB |
Output is correct |
| 27 |
Correct |
8 ms |
9440 KB |
Output is correct |
| 28 |
Correct |
8 ms |
9308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
720 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
1 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
860 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
2 ms |
860 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9052 KB |
Output is correct |
| 17 |
Correct |
9 ms |
9172 KB |
Output is correct |
| 18 |
Correct |
6 ms |
10328 KB |
Output is correct |
| 19 |
Correct |
10 ms |
10308 KB |
Output is correct |
| 20 |
Correct |
6 ms |
9564 KB |
Output is correct |
| 21 |
Correct |
8 ms |
10588 KB |
Output is correct |
| 22 |
Correct |
9 ms |
10328 KB |
Output is correct |
| 23 |
Correct |
11 ms |
9308 KB |
Output is correct |
| 24 |
Correct |
7 ms |
8332 KB |
Output is correct |
| 25 |
Correct |
7 ms |
9304 KB |
Output is correct |
| 26 |
Correct |
7 ms |
10564 KB |
Output is correct |
| 27 |
Correct |
8 ms |
9440 KB |
Output is correct |
| 28 |
Correct |
8 ms |
9308 KB |
Output is correct |
| 29 |
Correct |
344 ms |
157244 KB |
Output is correct |
| 30 |
Correct |
335 ms |
163180 KB |
Output is correct |
| 31 |
Correct |
367 ms |
164516 KB |
Output is correct |
| 32 |
Correct |
410 ms |
164684 KB |
Output is correct |
| 33 |
Correct |
347 ms |
144980 KB |
Output is correct |
| 34 |
Correct |
398 ms |
164712 KB |
Output is correct |
| 35 |
Correct |
443 ms |
180392 KB |
Output is correct |
| 36 |
Correct |
448 ms |
174540 KB |
Output is correct |
| 37 |
Correct |
441 ms |
180304 KB |
Output is correct |
