Submission #1081245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081245		Mkswll	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	448 ms	180392 KiB

joioi

#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
                vt <int> rec(n + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[i] = res;
                }

                if(flag) { // increasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int i = n; i >= 1; --i) {
                        int res = min(rec[i], last);
                        last = res;
                        mxx = max(mxx, smx[0][i][res + 1]);
                        mnn = min(mnn, smn[0][i][res + 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int i = 1; i <= n; ++i) {
                        int res = min(rec[i], last);
                        last = res;
                        mxx = max(mxx, smx[0][i][res + 1]);
                        mnn = min(mnn, smn[0][i][res + 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }

            }
            { // right side
                vt <int> rec(n + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[i] = res;

                }
                if(flag) { // increasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int i = n; i >= 1; --i) {
                        int res = max(rec[i], last);
                        last = res;
                        mxx = max(mxx, pmx[0][i][res - 1]);
                        mnn = min(mnn, pmn[0][i][res - 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int i = 1; i <= n; ++i) {
                        int res = max(rec[i], last);
                        last = res;
                        mxx = max(mxx, pmx[0][i][res - 1]);
                        mnn = min(mnn, pmn[0][i][res - 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
            }
            { // top side
                vt <int> rec(m + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[j] = res;

                }

                if(flag) { // increasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int j = m; j >= 1; --j) {
                        int res = min(rec[j], last);
                        last = res;

                        mxx = max(mxx, smx[1][res + 1][j]);
                        mnn = min(mnn, smn[1][res + 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int j = 1; j <= m; ++j) {
                        int res = min(rec[j], last);
                        last = res;

                        mxx = max(mxx, smx[1][res + 1][j]);
                        mnn = min(mnn, smn[1][res + 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
            }
            { // bottom side
                vt <int> rec(m + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[j] = res;


                }
                if(flag) { // increasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int j = m; j >= 1; --j) {
                        int res = max(rec[j], last);
                        last = res;

                        mxx = max(mxx, pmx[1][res - 1][j]);
                        mnn = min(mnn, pmn[1][res - 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int j = 1; j <= m; ++j) {
                        int res = max(rec[j], last);
                        last = res;

                        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
                vt <int> rec(n + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[i] = res;
                }

                if(flag) { // increasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int i = n; i >= 1; --i) {
                        int res = min(rec[i], last);
                        last = res;
                        mxx = max(mxx, smx[0][i][res + 1]);
                        mnn = min(mnn, smn[0][i][res + 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int i = 1; i <= n; ++i) {
                        int res = min(rec[i], last);
                        last = res;
                        mxx = max(mxx, smx[0][i][res + 1]);
                        mnn = min(mnn, smn[0][i][res + 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }

            }
            { // right side
                vt <int> rec(n + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[i] = res;

                }
                if(flag) { // increasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int i = n; i >= 1; --i) {
                        int res = max(rec[i], last);
                        last = res;
                        mxx = max(mxx, pmx[0][i][res - 1]);
                        mnn = min(mnn, pmn[0][i][res - 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int i = 1; i <= n; ++i) {
                        int res = max(rec[i], last);
                        last = res;
                        mxx = max(mxx, pmx[0][i][res - 1]);
                        mnn = min(mnn, pmn[0][i][res - 1]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
            }
            { // top side
                vt <int> rec(m + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[j] = res;

                }

                if(flag) { // increasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int j = m; j >= 1; --j) {
                        int res = min(rec[j], last);
                        last = res;

                        mxx = max(mxx, smx[1][res + 1][j]);
                        mnn = min(mnn, smn[1][res + 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = INF;
                    int mxx = 0, mnn = INF;
                    for(int j = 1; j <= m; ++j) {
                        int res = min(rec[j], last);
                        last = res;

                        mxx = max(mxx, smx[1][res + 1][j]);
                        mnn = min(mnn, smn[1][res + 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
            }
            { // bottom side
                vt <int> rec(m + 1, 0);
                bool flag = 1;
                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) {
                        flag = 0;
                        break;
                    }
                    rec[j] = res;


                }
                if(flag) { // increasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int j = m; j >= 1; --j) {
                        int res = max(rec[j], last);
                        last = res;

                        mxx = max(mxx, pmx[1][res - 1][j]);
                        mnn = min(mnn, pmn[1][res - 1][j]);
                    }
                    if(mxx - mnn <= x) return 1;
                }
                if(flag) { // decreasing
                    int last = 0;
                    int mxx = 0, mnn = INF;
                    for(int j = 1; j <= m; ++j) {
                        int res = max(rec[j], last);
                        last = res;

                        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;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40