Submission #146128

#	Time	Username	Problem	Language	Result	Execution time	Memory
146128		alextodoran	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1948 ms	148872 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+1;

const int NM_MAX = 2002;

int n, m;

int ma[NM_MAX][NM_MAX];

int minsub1[NM_MAX][NM_MAX];
int minsub2[NM_MAX][NM_MAX];

int maxc1[NM_MAX][NM_MAX];
int minc1[NM_MAX][NM_MAX];
int maxc2[NM_MAX][NM_MAX];
int minc2[NM_MAX][NM_MAX];

int ans = INF;

void f1 (int mi, int mx, int &a, int &b)
{
    int mia, mxa, mib, mxb;
    mia = mib = INF;
    mxa = mxb = -INF;
    int last = n;
    for(int j = 1; j <= m; j++)
    {
        int l = 0, r = last;
        while(l < r)
        {
            int mid = (l + r + 1) / 2;
            if(minc1[mid][j] < mi || maxc1[mid][j] > mx)
                r = mid - 1;
            else
                l = mid;
        }
        last = l;
        mia = min(mia, minc1[l][j]);
        mib = min(mib, minc2[l + 1][j]);
        mxa = max(mxa, maxc1[l][j]);
        mxb = max(mxb, maxc2[l + 1][j]);
    }
    if(mia == INF)
        mia = 0;
    if(mib == INF)
        mib = 0;
    if(mxa == INF)
        mxa = 0;
    if(mxb == INF)
        mxb = 0;
    a = mxa - mia;
    b = mxb - mib;
}

void f2 (int mi, int mx, int &a, int &b)
{
    int mia, mxa, mib, mxb;
    mia = mib = INF;
    mxa = mxb = -INF;
    int last = n;
    for(int j = m; j >= 1; j--)
    {
        int l = 0, r = last;
        while(l < r)
        {
            int mid = (l + r + 1) / 2;
            if(minc1[mid][j] < mi || maxc1[mid][j] > mx)
                r = mid - 1;
            else
                l = mid;
        }
        last = l;
        mia = min(mia, minc1[l][j]);
        mib = min(mib, minc2[l + 1][j]);
        mxa = max(mxa, maxc1[l][j]);
        mxb = max(mxb, maxc2[l + 1][j]);
    }
    if(mia == INF)
        mia = 0;
    if(mib == INF)
        mib = 0;
    if(mxa == INF)
        mxa = 0;
    if(mxb == INF)
        mxb = 0;
    a = mxa - mia;
    b = mxb - mib;
}

void solve (int val)
{
    int l = 0, r = ans - 1;
    int a, b;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        f1(val, val + mid, a, b);
        if(a > b)
            r = mid - 1;
        else
            l = mid;
    }
    f1(val, val + l, a, b);
    ans = min(ans, max(a, b));
    f1(val, val + l + 1, a, b);
    ans = min(ans, max(a, b));
    l = 0; r = ans - 1;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        f2(val, val + mid, a, b);
        if(a > b)
            r = mid - 1;
        else
            l = mid;
    }
    f2(val, val + l, a, b);
    ans = min(ans, max(a, b));
    f2(val, val + l + 1, a, b);
    ans = min(ans, max(a, b));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> ma[i][j];
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= m + 1; j++)
            minsub1[i][j] = minsub2[i][j] = INF;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            minsub1[i][j] = min(ma[i][j], min(minsub1[i][j - 1], minsub1[i - 1][j]));
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--)
            minsub2[i][j] = min(ma[i][j], min(minsub2[i][j + 1], minsub2[i - 1][j]));
    for(int j = 1; j <= m; j++)
    {
        maxc1[0][j] = -INF;
        for(int i = 1; i <= n; i++)
            maxc1[i][j] = max(ma[i][j], maxc1[i - 1][j]);
        maxc2[n + 1][j] = -INF;
        for(int i = n; i >= 1; i--)
            maxc2[i][j] = max(ma[i][j], maxc2[i + 1][j]);
    }
    for(int j = 1; j <= m; j++)
    {
        minc1[0][j] = INF;
        for(int i = 1; i <= n; i++)
            minc1[i][j] = min(ma[i][j], minc1[i - 1][j]);
        minc2[n + 1][j] = INF;
        for(int i = n; i >= 1; i--)
            minc2[i][j] = min(ma[i][j], minc2[i + 1][j]);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(ma[i][j] < minc1[i - 1][j] && ((ma[i][j] < minsub1[i - 1][j] && ma[i][j] < minsub1[i][j - 1]) ||
                                              (ma[i][j] < minsub2[i - 1][j] && ma[i][j] < minsub2[i][j + 1])))
                solve(ma[i][j]);
    cout << ans << "\n";
    return 0;
}

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