# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2005;
long long n,m,mn,mx,a[N][N],i1,j11,i2,j2,le,ri,mid,prmx[N][N],prmn[N][N],sfmn[N][N],sfmx[N][N];
long long mn1,mx1,mxx,mnn,l,r,mi,anss,anss1,idx,ww,j,ans,b[N],bbb[N],bb1[N],pr;
void rotate() {
for(int i=1;i<=n/2;i++){
for(int j=1;j<=m;j++){
swap(a[i][j],a[n-i+1][j]);
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
prmn[0][j]=1e10;
prmx[0][j]=-1e10;
prmn[i][j]=min(a[i][j],prmn[i-1][j]);
prmx[i][j]=max(a[i][j],prmx[i-1][j]);
if (mn>a[i][j]) {
i1=i;
j11=j;
mn=min(mn,a[i][j]);
}
if (mx<a[i][j]) {
i2=i;
j2=j;
mx=max(mx,a[i][j]);
}
}
}
for (int i=n; i>=1; i--) {
for (int j=1; j<=m; j++) {
sfmn[n+1][j]=1e10;
sfmx[n+1][j]=-1e10;
sfmn[i][j]=min(a[i][j],sfmn[i+1][j]);
sfmx[i][j]=max(a[i][j],sfmx[i+1][j]);
}
}
}
int check(int mid) {
/* l=1;
r=m;
while (l<=r) {
mi=(l+r)/2;
if (prmx[mi]<=mid+mn){
anss=mi;
l=mi+1;
} else {
r=mi-1;
}
}
l=1;
r=m;
while (l<=r) {
mi=(l+r)/2;
//cout<<mi<<" "<<sfmn[mi]<<endl;
if (sfmn[mi]>=mx-mid){
anss1=mi;
r=mi-1;
} else {
l=mi+1;
}
}
cout<<anss1<<endl;
if (anss>=anss1) return 1;
if (anss<anss1-1) return 0;
idx=n+1;ww=0;
for (int i=1; i<=n; i++) {
j=anss+1;
if(a[i][j]>mn+mid) {
idx=i;
break;
}
}
for (int i=n; i>=idx; i--) {
if (a[i][j]<mx-mid) {
ww=1;
}
}
if (!ww) return 1;
ww=0;
idx=0;
for (int i=n; i>=1; i--) {
j=anss+1;
if(a[i][j]>mn+mid) {
idx=i;
break;
}
}
for (int i=1; i<=idx; i++) {
if (a[i][j]<mx-mid) {
ww=1;
}
}
if (!ww) return 1;
return 0;
*/
int ww=0;
int bb=0;
int ss=0;
int id=0;
for (int j=1; j<=m; j++) {
id=n+1;
for (int i=1; i<=n; i++) {
if (prmx[i][j]>mn+mid) {
id=i;
break;
}
}
if (id!=n+1 && !bb) bb=j;
b[j]=id;
}
for (int j=1; j<=m; j++) {
if (b[j]==n+1 && bb<j) b[j]=n;
}
pr=1e10;
for (int j=1; j<=m; j++) {
pr=min(pr,b[j]);
bbb[j]=pr;
}
pr=1e10;
for (int j=m; j>=1; j--) {
pr=min(pr,b[j]);
bb1[j]=pr;
}
ww=0;
for (int j=1; j<=m; j++) {
if (bbb[j]==n+1) continue;
//cout<<j<<" "<<bbb[j]<<" "<<sfmn[bbb[j]][j]<<endl;
if (sfmn[bbb[j]][j]<mx-mid) {
ww++;
break;
}
}
for (int j=1; j<=m; j++) {
if (bb1[j]==n+1) continue;
// cout<<j<<" "<<b[j]<<" "<<sfmn[b[j]][j]<<endl;
if (sfmn[bb1[j]][j]<mx-mid) {
ww++;
break;
}
}
if (ww==2) return 0;
return 1;
}
int main() {
cin>>n>>m;
mn=1e10;
mx=-1e10;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
prmn[0][j]=1e10;
prmx[0][j]=-1e10;
cin>>a[i][j];
prmn[i][j]=min(a[i][j],prmn[i-1][j]);
prmx[i][j]=max(a[i][j],prmx[i-1][j]);
if (mn>a[i][j]) {
i1=i;
j11=j;
mn=min(mn,a[i][j]);
}
if (mx<a[i][j]) {
i2=i;
j2=j;
mx=max(mx,a[i][j]);
}
}
}
for (int i=n; i>=1; i--) {
for (int j=1; j<=m; j++) {
sfmn[n+1][j]=1e10;
sfmx[n+1][j]=-1e10;
sfmn[i][j]=min(a[i][j],sfmn[i+1][j]);
sfmx[i][j]=max(a[i][j],sfmx[i+1][j]);
}
}
ans=mx-mn;
le=0;
ri=ans;
while (le<=ri) {
mid=(le+ri)/2;
if (check(mid)) {
ri=mid-1;
ans=min(ans,mid);
} else {
le=mid+1;
}
}
rotate();
le=0;
ri=mx-mn;
while (le<=ri) {
mid=(le+ri)/2;
if (check(mid)) {
ri=mid-1;
ans=min(ans,mid);
} else {
le=mid+1;
}
}
cout<<ans<<endl;
}
Compilation message
joioi.cpp: In function 'int check(int)':
joioi.cpp:102:10: warning: unused variable 'ss' [-Wunused-variable]
102 | int ss=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
560 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
560 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
560 KB |
Output is correct |
| 6 |
Correct |
1 ms |
460 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
