// change bs limit
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 4e6;
int lo[2001][2001], hi[2001][2001], vec[2][2001][2001];
int calcLo[mn], calcHi[mn], prod;
pii coor[mn];
int get (int arr, pii it) {
return vec[arr][it.first][it.second];
}
bool check (int arr, int delta) {
int pos = -1, curLo = INT_MAX, curHi = INT_MIN;
for (int k = 0; k < prod; k++) {
int cur = get(arr, coor[k]);
while (pos + 1 < prod && get(arr, coor[pos + 1]) < cur - delta) {
int row, col; tie(row, col) = coor[++pos];
curLo = min(curLo, lo[row][col]);
curHi = max(curHi, hi[row][col]);
}
if (k + 1 < prod && get(arr, coor[k]) == get(arr, coor[k + 1])) continue;
int cHi = max(calcHi[k], curHi);
int cLo = min(calcLo[k], curLo);
if (cHi == INT_MIN || cHi - cLo <= delta) return 1;
}
return 0;
}
int solve (int arr, int n, int m) {
for (int i = 1; i <= n; i++)
lo[i][0] = INT_MAX, hi[i][0] = INT_MIN;
for (int j = 1; j <= m; j++) {
int loCol = INT_MAX, hiCol = INT_MIN;
for (int i = n; i >= 1; i--) {
lo[i][j] = min(lo[i][j - 1], loCol = min(loCol, vec[arr][i][j]));
hi[i][j] = max(hi[i][j - 1], hiCol = max(hiCol, vec[arr][i][j]));
}
}
int counter = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
coor[counter++] = make_pair(i, j);
function<bool(pii a, pii b)> comp = [&] (pii a, pii b) {
return get(arr, a) < get(arr, b);
};
sort(coor, coor + prod, comp);
int curLo = INT_MAX, curHi = INT_MIN;
for (int k = prod - 1; k >= 0; k--) {
calcLo[k] = curLo, calcHi[k] = curHi;
int row, col; tie(row, col) = coor[k];
curLo = min(curLo, lo[row][col]);
curHi = max(curHi, hi[row][col]);
}
if (check(arr, 0)) return 0;
int ans = 0;
for (int i = 5; i >= 0; i--)
if (!check(arr, ans | (1 << i))) ans |= (1 << i);
return ans + 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
prod = n * m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> vec[0][i][j];
vec[1][j][n - i + 1] = vec[0][i][j];
}
}
cout << min(solve(0, n, m), solve(1, m, n));
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
