Submission #1081195

#TimeUsernameProblemLanguageResultExecution timeMemory
1081195MkswllThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
1 ms8796 KiB
#include <bits/stdc++.h> using namespace std; #define vt vector #define F first #define S second #define pb push_back #define all(v) v.begin(), v.end() typedef long long ll; typedef pair <int, int> pii; const int MAXN = 2e3 + 5, INF = 1e9 + 5; int n, m, k; int a[MAXN][MAXN]; pii mx {1, 1}, mn {1, 1}; int pmx[2][MAXN][MAXN], smx[2][MAXN][MAXN], pmn[2][MAXN][MAXN], smn[2][MAXN][MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { cin >> a[i][j]; if(a[i][j] > a[mx.F][mx.S]) mx = {i, j}; if(a[i][j] < a[mn.F][mn.S]) mn = {i, j}; } } for(int i = 1; i <= n; ++i) { pmn[0][i][0] = INF; smn[0][i][m + 1] = INF; for(int j = 1; j <= m; ++j) { pmx[0][i][j] = max(pmx[0][i][j - 1], a[i][j]); pmn[0][i][j] = min(pmn[0][i][j - 1], a[i][j]); } for(int j = m; j >= 1; --j) { smx[0][i][j] = max(smx[0][i][j + 1], a[i][j]); smn[0][i][j] = min(smn[0][i][j + 1], a[i][j]); } } for(int j = 1; j <= m; ++j) { pmn[1][0][j] = INF; smn[1][n + 1][j] = INF; for(int i = 1; i <= n; ++i) { pmx[1][i][j] = max(pmx[1][i - 1][j], a[i][j]); pmn[1][i][j] = min(pmn[1][i - 1][j], a[i][j]); } for(int i = n; i >= 1; --i) { smx[1][i][j] = max(smx[1][i + 1][j], a[i][j]); smn[1][i][j] = min(smn[1][i + 1][j], a[i][j]); } } auto check = [](int x) -> bool { { // fix mn int up = a[mn.F][mn.S] + x; { // left side int mxx = 0, mnn = INF; for(int i = 1; i <= n; ++i) { int l = 1, r = m, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(pmx[0][i][mid] <= up) { res = mid; l = mid + 1; } else r = mid - 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, smx[0][i][res + 1]); mnn = min(mnn, smn[0][i][res + 1]); } if(mxx - mnn <= x) return 1; } { // right side int mxx = 0, mnn = INF; for(int i = 1; i <= n; ++i) { int l = 1, r = m, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(smx[0][i][mid] <= up) { res = mid; r = mid - 1; } else l = mid + 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, pmx[0][i][res - 1]); mnn = min(mnn, pmn[0][i][res - 1]); } if(mxx - mnn <= x) return 1; } { // top side int mxx = 0, mnn = INF; for(int j = 1; j <= m; ++j) { int l = 1, r = n, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(pmx[1][mid][j] <= up) { res = mid; l = mid + 1; } else r = mid - 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, smx[1][res + 1][j]); mnn = min(mnn, smn[1][res + 1][j]); } if(mxx - mnn <= x) return 1; } { // bottom side int mxx = 0, mnn = INF; for(int j = 1; j <= m; ++j) { int l = 1, r = n, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(smx[1][mid][j] <= up) { res = mid; r = mid - 1; } else l = mid + 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, pmx[1][res - 1][j]); mnn = min(mnn, pmn[1][res - 1][j]); } if(mxx - mnn <= x) return 1; } } { // fix mx int lo = a[mx.F][mx.S] - x; { // left side int mxx = 0, mnn = INF; for(int i = 1; i <= n; ++i) { int l = 1, r = m, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(pmn[0][i][mid] >= lo) { res = mid; l = mid + 1; } else r = mid - 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, smx[0][i][res + 1]); mnn = min(mnn, smn[0][i][res + 1]); } if(mxx - mnn <= x) return 1; } { // right side int mxx = 0, mnn = INF; for(int i = 1; i <= n; ++i) { int l = 1, r = m, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(smn[0][i][mid] >= lo) { res = mid; r = mid - 1; } else l = mid + 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, pmx[0][i][res - 1]); mnn = min(mnn, pmn[0][i][res - 1]); } if(mxx - mnn <= x) return 1; } { // top side int mxx = 0, mnn = INF; for(int j = 1; j <= m; ++j) { int l = 1, r = n, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(pmn[1][mid][j] >= lo) { res = mid; l = mid + 1; } else r = mid - 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, smx[1][res + 1][j]); mnn = min(mnn, smn[1][res + 1][j]); } if(mxx - mnn <= x) return 1; } { // bottom side int mxx = 0, mnn = INF; for(int j = 1; j <= m; ++j) { int l = 1, r = n, res = -1; while(l <= r) { int mid = (l + r) >> 1; if(smn[1][mid][j] >= lo) { res = mid; r = mid - 1; } else l = mid + 1; } if(res == -1) { mxx = INF; mnn = -INF; break; } mxx = max(mxx, pmx[1][res - 1][j]); mnn = min(mnn, pmn[1][res - 1][j]); } if(mxx - mnn <= x) return 1; } } return 0; }; int l = 0, r = 1e9, ans = 1e9; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...