oj.uz

답안 #146120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146120 2019-08-22T09:33:14 Z alextodoran The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+1;

const int NM_MAX = 1002;

int n, m;

int ma[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) / 2;
        f1(val, val + mid, a, b);
        if(a < b)
            l = mid + 1;
        else
            r = 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) / 2;
        f2(val, val + mid, a, b);
        if(a < b)
            l = mid + 1;
        else
            r = 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()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> ma[i][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][j])
                solve(ma[i][j]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Incorrect 2 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -