#include<bits/stdc++.h>
using namespace std;
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define vii vector<pii>
#define pb push_back
#define vi vector<int>
const int mx = 2000;
const int inf = 1e15;
const int LOG = 22;
int n, m;
int grid[mx][mx];
int prefmin1[mx][mx];
int prefmin[mx][mx];
int prefmin2[mx][mx];
int prefmin3[mx][mx];
int prefmax1[mx][mx];
int prefmax[mx][mx];
int prefmax2[mx][mx];
int prefmax3[mx][mx];
vector<vi> v;
void preprocess(){
for(int i = 0; i < n;i++){
for(int j = 0;j < m;j++){
int x = inf, y = inf;
if(i > 0)x = prefmin[i-1][j];
if(j > 0)y = prefmin[i][j-1];
prefmin[i][j] = min(x, y);
prefmin[i][j] = min(prefmin[i][j], grid[i][j]);
}
}
for(int i = 0; i < n;i++){
for(int j = 0;j < m;j++){
int x = 0, y = 0;
if(i > 0)x = prefmax[i-1][j];
if(j > 0)y = prefmax[i][j-1];
prefmax[i][j] = max(x, y);
prefmax[i][j] = max(prefmax[i][j], grid[i][j]);
}
}
// 1 :
for(int i = n-1; i >= 0;i--){
for(int j = 0;j < m;j++){
int x = inf, y = inf;
if((i+1) < n)x = prefmin1[i+1][j];
if(j > 0)y = prefmin1[i][j-1];
prefmin1[i][j] = min(x, y);
prefmin1[i][j] = min(prefmin1[i][j], grid[i][j]);
}
}
for(int i = n-1; i >= 0;i--){
for(int j = 0;j < m;j++){
int x = 0, y = 0;
if((i+1) < n)x = prefmax1[i+1][j];
if(j > 0)y = prefmax1[i][j-1];
prefmax1[i][j] = max(x, y);
prefmax1[i][j] = max(prefmax1[i][j], grid[i][j]);
}
}
// 2 :
for(int i = 0; i < n;i++){
for(int j = m-1;j >= 0;j--){
int x = inf, y = inf;
if(i > 0)x = prefmin2[i-1][j];
if((j+1) < m)y = prefmin2[i][j+1];
prefmin2[i][j] = min(x, y);
prefmin2[i][j] = min(prefmin2[i][j], grid[i][j]);
}
}
for(int i = 0; i < n;i++){
for(int j = m-1;j >= 0;j--){
int x = 0, y = 0;
if(i > 0)x = prefmax2[i-1][j];
if((j+1) < m)y = prefmax2[i][j+1];
prefmax2[i][j] = max(x, y);
prefmax2[i][j] = max(prefmax2[i][j], grid[i][j]);
}
}
// 3:
for(int i = n-1; i >= 0;i--){
for(int j = m-1;j >= 0;j--){
int x = inf, y = inf;
if((i+1) < n)x = prefmin3[i+1][j];
if((j+1) < m)y = prefmin3[i][j+1];
prefmin3[i][j] = min(x, y);
prefmin3[i][j] = min(prefmin3[i][j], grid[i][j]);
}
}
for(int i = n-1; i >= 0;i--){
for(int j = m-1;j >= 0;j--){
int x = 0, y = 0;
if((i+1) < n)x = prefmax3[i+1][j];
if((j+1) < m)y = prefmax3[i][j+1];
prefmax3[i][j] = max(x, y);
prefmax3[i][j] = max(prefmax3[i][j], grid[i][j]);
}
}
}
int32_t main(){
init();
cin.tie();cout.tie();ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 0; i < n;i++){
for(int j = 0;j < m;j++){
cin >> grid[i][j];
v.pb({grid[i][j], i, j});
}
}
preprocess();
int res = inf;
sort(v.begin(), v.end());
int a = inf, b = -inf;
for(int i = 0; i < v.size();i++){
if(i > 0){
int x = v[i-1][1], y = v[i-1][2];
a = min(a, prefmin[x][y]);
b = max(b, prefmax[x][y]);
}
res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
}
a = inf, b = -inf;
for(int i = 0; i < v.size();i++){
if(i > 0){
int x = v[i-1][1], y = v[i-1][2];
a = min(a, prefmin1[x][y]);
b = max(b, prefmax1[x][y]);
}
res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
}
a = inf, b = -inf;
for(int i = 0; i < v.size();i++){
if(i > 0){
int x = v[i-1][1], y = v[i-1][2];
a = min(a, prefmin2[x][y]);
b = max(b, prefmax2[x][y]);
}
res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
}
a = inf, b = -inf;
for(int i = 0; i < v.size();i++){
if(i > 0){
int x = v[i-1][1], y = v[i-1][2];
a = min(a, prefmin3[x][y]);
b = max(b, prefmax3[x][y]);
}
res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
}
cout << res << endl;
}
Compilation message
joioi.cpp: In function 'int32_t main()':
joioi.cpp:131:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i = 0; i < v.size();i++){
| ~~^~~~~~~~~~
joioi.cpp:140:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i = 0; i < v.size();i++){
| ~~^~~~~~~~~~
joioi.cpp:149:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 0; i < v.size();i++){
| ~~^~~~~~~~~~
joioi.cpp:158:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0; i < v.size();i++){
| ~~^~~~~~~~~~
joioi.cpp: In function 'void init()':
joioi.cpp:6:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:8:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
