oj.uz

답안 #46691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46691 2018-04-22T15:03:05 Z kuzmichev_dima The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 21 ms 16308 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

const int maxn = 2005;
const int inf = 1e9+7;

pii prec[maxn][maxn];
int n, m;
int a[maxn][maxn];
int b[maxn][maxn];
int global_min, global_max;

struct Event {
    int minn, row, diff;
};

bool operator < (Event fi, Event se) {
    return fi.minn < se.minn;
}

bool check(int delta) {
    //fprintf(stderr, "check %d\n", delta);
    vector<Event> events;
    vi app_limits(m, -inf);
    forn(i, n) {
        int cur_app = -inf;
        int cur_dis = inf;
        forn(j, m) {
            //min <= x <= min + delta
            cur_app = max(cur_app, a[i][j] - delta);

            cur_app = max(cur_app, app_limits[j]);
            app_limits[j] = max(app_limits[j], cur_app);

            cur_dis = min(cur_dis, a[i][j] + 1);
            if (cur_app < cur_dis) {
                events.pb({cur_app, i, +1});
                events.pb({cur_dis, i, -1});
            }
        }
    }
    sort(events.begin(), events.end());
    /*for (auto e : events) {
        fprintf(stderr, "event minn = %d row = %d diff = %d\n", e.minn, e.row, e.diff);
    }*/
    multiset<int> right_part;
    forn(i, n)
        forn(j, m)
            right_part.insert(a[i][j]);
    size_t pointer = 0;
    vi rows(n);
    while(pointer < events.size()) {
        int minn = events[pointer].minn;
        while(pointer < events.size() && events[pointer].minn == minn) {
            int row = events[pointer].row;
            rows[row] += events[pointer].diff;
            if (events[pointer].diff == 1)
                right_part.erase(right_part.find(a[row][rows[row] - 1]));
            else
                right_part.insert(a[row][rows[row]]);
            pointer++;
        }
        /*printf("minn = %d\n", minn);
        forn(i, n)
            printf("rows[%d] = %d\n", i, rows[i]);*/
        if (right_part.empty())
            return true;
        int right_min = *right_part.begin();
        int right_max = *right_part.rbegin();
        if (right_max - right_min <= delta)
            return true;
    }
    return false;
}

int solve() {
    forn(i, n) {
        prec[i][m] = {inf, -inf};
        for (int len = m - 1; len >= 0; --len) {
            prec[i][len] = {min(prec[i][len + 1].fi, a[i][len]),
                            max(prec[i][len + 1].se, a[i][len])};
            //printf("prec[%d][%d] = %d %d\n", i, len, prec[i][len].fi, prec[i][len].se);
        }
    }

    int start = 0;
    int finish = global_max - global_min;
    while(start < finish) {
        int middle = (start + finish) / 2;
        if (check(middle)) {
            finish = middle;
        } else {
            start = middle + 1;
        }
    }
    return start;
}


int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    //freopen("outp", "w", stdout);
#else
    // freopen(TASKNAME ".in", "r", stdin);
    // freopen(TASKNAME ".out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    global_min = inf;
    global_max = -inf;
    forn(i, n)
        forn(j, m) {
            scanf("%d", &a[i][j]);
            global_min = min(global_min, a[i][j]);
            global_max = max(global_max, a[i][j]);
        }
    int first = solve();
    forn(i, n)
        forn(j, m)
            b[n - i - 1][j] = a[i][j];
    memcpy(a, b, sizeof(b));
    /*forn(i, n) {
        forn(j, m)
            printf("%d ", b[i][j]);
        printf("\n");
    }*/
    int second = solve();
    //printf("first = %d second = %d\n", first, second);
    printf("%d", min(first, second));
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:140:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 16120 KB Output is correct
2 Correct 21 ms 16232 KB Output is correct
3 Incorrect 19 ms 16308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 16120 KB Output is correct
2 Correct 21 ms 16232 KB Output is correct
3 Incorrect 19 ms 16308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 16120 KB Output is correct
2 Correct 21 ms 16232 KB Output is correct
3 Incorrect 19 ms 16308 KB Output isn't correct
4 Halted 0 ms 0 KB -