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>
using namespace std;
using ll = long long;
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N=2010,INF=2e9;
int h,w,a[N][N],t[N][N];
int gmin=INF,gmax;
void rotate() {
memset(t,0,sizeof t);
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
t[j][h-i+1]=a[i][j];
}
}
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
a[i][j]=t[i][j];
}
}
}
bool testmn(int ans) {
vector<vector<int>> mn(h+10,vector<int>(w+10,INF));
for (int i = 1; i <= w; ++i) {
for (int j = h; j >= 1; --j) {
mn[j][i]=min(mn[j+1][i],a[j][i]);
}
}
vector<int> stop(h+1);
int r=1,c=1;
while (1) {
while (c<=w&&mn[r][c]>=gmax-ans) {
stop[r]=c++;
}
if (c>w) break;
while (r<=h&&mn[r][c]<gmax-ans) {
stop[r++]=c-1;
}
if (r>h) break;
}
int mx = 0;
for (int i = 1; i <= h; ++i) {
for (int j = w; j >= 1; --j) {
if (j==stop[i]) break;
chmax(mx,a[i][j]);
}
}
return (mx<=gmin+ans);
}
bool testmx(int ans) {
vector<vector<int>> mx(h+10,vector<int>(w+10));
for (int i = 1; i <= w; ++i) {
for (int j = h; j >= 1; --j) {
mx[j][i]=max(mx[j+1][i],a[j][i]);
}
}
vector<int> stop(h+1);
int r=1,c=1;
while (1) {
while (c<=w&&mx[r][c]<=gmin+ans) {
stop[r]=c++;
}
if (c>w) break;
while (r<=h&&mx[r][c]>gmin+ans) {
stop[r++]=c-1;
}
if (r>h) break;
}
int mn = INF;
for (int i = 1; i <= h; ++i) {
for (int j = w; j >= 1; --j) {
if (j==stop[i]) break;
chmin(mn,a[i][j]);
}
}
return (mn>=gmax-ans);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin.exceptions(ios::badbit|ios::failbit);
cin >> h >> w;
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
cin >> a[i][j];
chmin(gmin,a[i][j]);
chmax(gmax,a[i][j]);
}
}
ll lo = 0, hi = 1e9+1;
while (lo+1<hi) {
ll mid = (lo+hi)>>1ll;
bool ok = false;
for (int i = 0; i < 3; ++i) {
ok|=testmx(mid);
ok|=testmn(mid);
rotate();
}
ok|=testmx(mid);
ok|=testmn(mid);
if (ok) hi = mid;
else lo = mid;
}
cout << hi;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |