Submission #399893

#	Time	Username	Problem	Language	Result	Execution time	Memory
399893		lukameladze	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2853 ms	196256 KiB

joioi

# 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;
     }
    
    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=ans;
     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 (stderr)

joioi.cpp: In function 'int check(int)':
joioi.cpp:102:10: warning: unused variable 'ss' [-Wunused-variable]
  102 |      int ss=0;
      |          ^~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40