# 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;
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;
*/
ww=0;
for (int j=1; j<=m; j++) {
for (int i=1; i<=n; i++) {
if (prmx[i][j]>mn+mid) {
if (i==1 && j!=ww+1) return 0;
if (i==1) ww=j;
if (sfmn[i][j]<mx-mid) {
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=mx-mn;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
