# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
902626 | Maite_Morale | 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 MAX 3000
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
ll tmn[5][MAX][MAX]={},tmx[5][MAX][MAX]={},a[MAX][MAX]={},m,n;
ll v[5000006];map<ll,ll> mp;
ll OK(ll x,ll z){
ll cl=-1,mx=0,mn=oo;
for(int i=0;i<n;i++){
while(cl+1<m && tmn[0][i][cl+1]<x)cl++;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}
mn=min(mn,mx);cl=m;mx=0;
for(int i=0;i<n;i++){
while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--;
mx=max(mx,tmx[0][i][cl]);
}
mn=min(mn,mx);cl=-1;mx=0;
for(int i=n-1;i>=0;i--){
while(cl+1<m && tmn[0][i][cl+1]<x)cl++;
if(cl!=-1)mx=max(mx,tmx[1][i][cl]);
}
mn=min(mn,mx);cl=m;mx=0;
for(int i=n-1;i>=0;i--){
while(cl-1>=0 && tmn[1][i][cl-1]<x)cl--;
mx=max(mx,tmx[0][i][cl]);
}
mn=min(mn,mx);
if(z==1)return max(abs(v[0]-mn),abs(v.back()-x));
if(abs(v[0]-mn)<=abs(v.back()-x))return 1;
return 0;
}
int main(){
fast_in
cin>>n>>m;ll c=0;
for(int i=0;i<n;i++){
tmn[0][i][m]=tmn[1][i][0]=oo;
tmx[0][i][m]=tmx[1][i][0]=0;
for(int j=0;j<m;j++){
cin>>a[i][j];
if(mp[a[i][j]]==0){
mp[a[i][j]]=1;
v[c]=a[i][j];
c++;
}
tmx[1][i][j]=max(tmx[1][i][j],a[i][j]);
tmx[1][i][j+1]=tmx[1][i][j];
tmn[1][i][j]=min(tmn[1][i][j],a[i][j]);
tmn[1][i][j+1]=tmn[1][i][j];
}
for(int j=m-1;j>=0;j--){
tmx[0][i][j]=max(tmx[0][i][j+1],a[i][j]);
tmn[0][i][j]=min(tmn[0][i][j+1],a[i][j]);
}
}
sort(v,v+c);
if(c==1){cout<<0;return 0;}
ll p=1,f=c;
while(abs(f-p)!=1){
ll md=(p+f)/2;
if(md<0 || md>=c)while(true){md=md;}
if(OK(v[md],0)==1)p=md;
else f=md;
}
if(f==c){cout<<OK(v[p],1);return 0;}
cout<<min(OK(v[p],1),OK(v[f],1));
return 0;
}