#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'
typedef long long int ll;
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 2e3 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;
typedef long long int lli;
typedef pair<int,int> pii;
vector <pair <int,pii> > v;
deque <pair <int,pii> > Q;
pair <int,pii> temp[2];
int n,m,a[N][N],mnn[N][2],mxn[N][2],mnm[N][2],mxm[N][2];
bool check(int l1,int r1,int l2,int r2) {
if (l2 > l1 && l2 < r1) return true;
if (r2 > l1 && r2 < r1) return true;
if (l1 > l2 && l1 < r2) return true;
if (r1 > l2 && r1 < r2) return true;
return false;
}
int main() {
scanf("%d %d",&n,&m);
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= m ; j++) {
scanf("%d",&a[i][j]);
v.pb(mp(a[i][j],mp(i,j)));
}
for (int i = 1 ; i <= n ; i++)
for (int j = 0 ; j < 2 ; j++)
mnn[i][j] = INF , mxn[i][j] = -INF;
for (int i = 1 ; i <= m ; i++)
for (int j = 0 ; j < 2 ; j++)
mnm[i][j] = INF , mxm[i][j] = -INF;
sort(v.begin(),v.end());
for (auto i : v)
Q.push_back(i);
temp[0] = Q.front();
temp[1] = Q.back();
for (int i = 0 ; i < 2 ; i++) {
mnn[temp[i].sc.fi][i] = temp[i].sc.sc;
mxn[temp[i].sc.fi][i] = temp[i].sc.sc;
mnm[temp[i].sc.sc][i] = temp[i].sc.fi;
mxm[temp[i].sc.sc][i] = temp[i].sc.fi;
}
Q.pop_front(); Q.pop_back();
while(len(Q)) {
auto tutmn = Q.front();
auto tutmx = Q.back();
if (temp[1].fi - tutmn.fi >= tutmx.fi - temp[0].fi) {
int val = tutmn.fi, i = tutmn.sc.fi, j = tutmn.sc.sc;
mnn[i][0] = min(mnn[i][0],j);
mxn[i][0] = max(mxn[i][0],j);
mnm[j][0] = min(mnm[j][0],i);
mxm[j][0] = max(mxm[j][0],i);
if (check(mnn[i][0],mxn[i][0],mnn[i][1],mxn[i][1]) || check(mnm[j][0],mxm[j][0],mnm[j][1],mxm[j][1])) {
printf("%d\n",temp[1].fi - val);
return 0;
}
Q.pop_front();
}
else {
int val = tutmx.fi, i = tutmx.sc.fi, j = tutmx.sc.sc;
mnn[i][1] = min(mnn[i][1],j);
mxn[i][1] = max(mxn[i][1],j);
mnm[j][1] = min(mnm[j][1],i);
mxm[j][1] = max(mxm[j][1],i);
Q.pop_back();
if (check(mnn[i][0],mxn[i][0],mnn[i][1],mxn[i][1]) || check(mnm[j][0],mxm[j][0],mnm[j][1],mxm[j][1])) {
printf("%d\n",val - temp[0].fi);
return 0;
}
}
}
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
joioi.cpp:52:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
