| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 399804 | lukameladze | The Kingdom of JOIOI (JOI17_joioi) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# 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,j1,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]=1e9;
prmx[0][j]=-1e9;
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;
j1=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]=1e9;
sfmx[n+1][j]=-1e9;
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;
*/
for (int j=1; j<=m; j++) {
for (int i=1; i<=n; i++) {
if (prmx[i][j]>mn+mid) {
if (sfmn[i][j]<mx-mid) {
return 0;
}
}
}
}
return 1;
}
int main() {
cin>>n>>m;
mn=1e9;
mx=-1e9;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
prmn[0][j]=1e9;
prmx[0][j]=-1e9;
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;
j1=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]=1e9;
sfmx[n+1][j]=-1e9;
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=1;
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=1;
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;
}