[LOJ2334] 「JOI 2017 Final」JOIOI 王国（二分答案）
#include<bits/stdc++.h>
using namespace std;
int read()
{
int _ = 0, __ = getchar(), ___ = 1;
for(; !isdigit(__); __ = getchar()) if(__ == '-') ___ = -1;
for(; isdigit(__); __ = getchar()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
return _ * ___;
}
const int N = 2000 + 7;
int premax[N][N], sufmax[N][N], premin[N][N], sufmin[N][N];
int tmp[N], n, m, mn = tmp[0] = 2e9, mx = -2e9;
bool check1(int lim)
{
int mnlim = mn + lim, mxlim = mx - lim, lst = m;
for(int i = 1; i <= n; ++ i)
{
tmp[i] = 0;
for(int j = 1; j <= m; ++ j)
if(premax[i][j] <= mnlim)
tmp[i] = j;
}
for(int i = n; i >= 1; -- i)
{
lst = min(tmp[i], lst);
if(sufmin[i][lst + 1] < mxlim)
return false;
}
return true;
}
bool check2(int lim)
{
int mnlim = mn + lim, mxlim = mx - lim, lst = m;
for(int i = 1; i <= n; ++ i)
{
tmp[i] = 0;
for(int j = 1; j <= m; ++ j)
if(premin[i][j] >= mxlim)
tmp[i] = j;
}
for(int i = n; i >= 1; -- i)
{
lst = min(tmp[i], lst);
if(sufmax[i][lst + 1] > mnlim)
return false;
}
return true;
}
bool check3(int lim)
{
int mnlim = mn + lim, mxlim = mx - lim, lst = m;
for(int i = 1; i <= n; ++ i)
{
tmp[i] = 0;
for(int j = 1; j <= m; ++ j)
if(premax[i][j] <= mnlim)
tmp[i] = j;
}
for(int i = 1; i <= n; ++ i)
{
lst = min(tmp[i], lst);
if(sufmin[i][lst + 1] < mxlim)
return false;
}
return true;
}
bool check4(int lim)
{
int mnlim = mn + lim, mxlim = mx - lim, lst = m;
for(int i = 1; i <= n; ++ i)
{
tmp[i] = 0;
for(int j = 1; j <= m; ++ j)
if(premin[i][j] >= mxlim)
tmp[i] = j;
}
for(int i = 1; i <= n; ++ i)
{
lst = min(tmp[i], lst);
if(sufmax[i][lst + 1] > mnlim)
return false;
}
return true;
}
bool check(int lim)
{
if(check1(lim) || check2(lim) || check3(lim) || check4(lim))
return true;
return false;
}
int main()
{
//freopen("", "r", stdin);
//freopen("", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; ++ j)
{
premax[i][j] = premin[i][j] = sufmax[i][j] = sufmin[i][j] = read();
if(premax[i][j] > mx)
mx = premax[i][j];
if(premin[i][j] < mn)
mn = premin[i][j];
}
sufmin[i][m + 1] = 2e9;
}
for(int i = 1; i <= n; ++ i)
{
for(int j = 2; j <= m; ++ j)
{
premax[i][j] = max(premax[i][j - 1], premax[i][j]);
premin[i][j] = min(premin[i][j - 1], premin[i][j]);
}
for(int j = m; j >= 2; -- j)
{
sufmax[i][j - 1] = max(sufmax[i][j], sufmax[i][j - 1]);
sufmin[i][j - 1] = min(sufmin[i][j], sufmin[i][j - 1]);
}
}
int l = 0, r = mx - mn, ans;
while(l <= r)
{
int mid = (l + r) >> 1;
if(check(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
printf("%d\n", ans);
return 0;
}