#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
ll n,m;
ll fld[2020][2020];
ll ldp[2020][2020];
ll rdp[2020][2020];
ll rm1[1010101];
ll lm1[1010101];
ll rm2[1010101];
ll lm2[1010101];
vector<ll> x;
vector<ll> y;
bool can(ll l,ll r){
ll i,j;
for(i=0;i<=n+1;i++){
for(j=0;j<=m+1;j++)
ldp[i][j]=rdp[i][j]=0;
ldp[i][0]=rdp[i][m+1]=3;
}
for(i=1;i<=n;i++){
lm1[i]=lm2[i]=1e9;
rm1[i]=rm2[i]=-1;
}
//cout<<"yaho"<<endl;
for(i=1;i<=n;i++){
//cout<<"yaho"<<endl;
for(j=1;j<=m;j++){
if(fld[i][j]<=l) ldp[i][j]+=1;
if(fld[i][j]>=r) ldp[i][j]+=2;
ldp[i][j]&=ldp[i][j-1];
}
//cout<<"yaho"<<endl;
for(j=m;j>=1;j--){
if(fld[i][j]<=l) rdp[i][j]+=2;
if(fld[i][j]>=r) rdp[i][j]+=1;
rdp[i][j]&=rdp[i][j+1];
}
//cout<<"yaho"<<endl;
for(j=0;j<=m;j++){
if(ldp[i][j]&rdp[i][j+1]&1) lm1[i]=min(lm1[i],j);
if(ldp[i][j]&rdp[i][j+1]&2) lm2[i]=min(lm2[i],j);
if(ldp[i][j]&rdp[i][j+1]&1) rm1[i]=max(rm1[i],j);
if(ldp[i][j]&rdp[i][j+1]&2) rm2[i]=max(rm2[i],j);
}
if(i!=1){
lm1[i]=max(lm1[i],lm1[i-1]);
lm2[i]=max(lm2[i],lm2[i-1]);
rm1[i]=min(rm1[i],rm1[i-1]);
rm2[i]=min(rm2[i],rm2[i-1]);
}
//cout<<"yaho"<<endl;
}
if(lm1[n]<=m||lm2[n]<=m||rm1[n]>=0||rm2[n]>=0)
return true;
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
ll i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
cin>>fld[i][j];
x.pb(fld[i][j]);
}
compress(x);
ll sz=x.size();
ll ans=x[sz-1];
for(i=1;i<sz;i++)
y.pb(x[i]-x[0]);
y.pb(0);
for(i=1;i<sz-1;i++)
y.pb(x[sz-1]-x[i]);
compress(y);
ll lo=0,hi=y.size();
while(lo<hi){
ll mi=(lo+hi)/2;
ll mid=y[mi];
ll l=x[0]+mid;
ll r=x[sz-1]-mid;
ll lidx=upper_bound(x.begin(), x.end(),l)-x.begin();
ll ridx=lower_bound(x.begin(), x.end(),r)-x.begin();
//cout<<lo<<' '<<hi<<' '<<mi<<' '<<mid<<' '<<l<<' '<<r<<' '<<lidx<<' '<<ridx<<endl;
if(lidx<ridx){
lo=mi+1;
continue;
}
if(can(l,r)){
hi=mi;
ans=min(ans,mid);
}
else lo=mi+1;
}
cout<<ans;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:88:9: warning: unused variable 'k' [-Wunused-variable]
88 | ll i,j,k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
