Submission #459624

#	Time	Username	Problem	Language	Result	Execution time	Memory
459624		TeaTime	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	4 ms	716 KiB

joioi

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2050, INF = 1e9 * 1e9;
ll grid[SZ][SZ], pt[SZ];
vector<tuple<ll, ll, ll>> vec;
ll n, m, mx;
pair<ll, ll> pos;

void inc(ll ht) {
    while (pt[ht + 1] < pt[ht] + 1) {
        inc(ht + 1);
        if (mx == INF) return;
    }

    if (make_pair(ht, pt[ht]) == pos) {
        mx = INF;
        pt[ht] = INF;
        return;
    }

    mx = max(mx, grid[ht][pt[ht]]);
    pt[ht]++;
}

ll find() {
    pt[n] = INF;

    mx = get<0>(vec[0]);
    pos = { get<1>(vec.back()), get<2>(vec.back()) };
    ll ans = INF, st = get<0>(vec.back());

    for (int i = 0; i < vec.size(); i++) {
        ll x = get<1>(vec[i]), y = get<2>(vec[i]);
        while (pt[x] <= y) {
            inc(x);
        }
        if (mx == INF) break;

        ans = min(ans, max(mx - get<0>(vec[0]), st - get<0>(vec[i + 1])));
    }
    return ans;
}

int main() {
    fastInp;

    cin >> n >> m;

    pair<ll, ll> cur = { INF, -INF };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            cur.first = min(cur.first, grid[i][j]);
            cur.second = max(cur.second, grid[i][j]);
        }
    }

    vec.clear();
    for (int i = 0; i < n; i++) {
        pt[i] = 0;
        for (int j = 0; j < m; j++) {
            vec.push_back({ grid[i][j], i, j });
        }
    }

    sort(vec.begin(), vec.end());
    ll ans = (cur.second - cur.first);

    ans = min(ans, find());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll snd = m - j - 1;
            if (j < snd) swap(grid[i][j], grid[i][snd]);
        }
    }
    for (auto& c : vec) get<1>(c) = m - get<1>(c) - 1;

    ans = min(ans, find());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll snd = n - i - 1;
            if (i < snd) swap(grid[i][j], grid[snd][j]);
        }
    }
    for (auto& c : vec) get<0>(c) = n - get<0>(c) - 1;

    ans = min(ans, find());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll snd = m - j - 1;
            if (j < snd) swap(grid[i][j], grid[i][snd]);
        }
    }
    for (auto& c : vec) get<1>(c) = m - get<1>(c) - 1;
    for (auto& c : vec) get<0>(c) = n - get<0>(c) - 1;

    ans = min(ans, find());

    cout << ans;

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'll find()':
joioi.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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