oj.uz

Submission #862889

# Submission time Handle Problem Language Result Execution time Memory
862889 2023-10-19T09:27:42 Z green_gold_dog The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2156 ms 188288 KB 
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

ll get(set<pair<ll, pair<ll, ll>>>& s) {
        if (s.empty()) {
                return 0;
        }
        return s.rbegin()->first - s.begin()->first;
}

ll sol(ll n, ll m, vector<vector<ll>>& arr) {
        vector<tuple<ll, ll, ll>> s1;
        vector<vector<ll>> dels;
        ll mi = INF32, ma = 0;
        for (ll i = 0; i < n; i++) {
                for (ll j = 0; j < m; j++) {
                        s1.emplace_back(arr[i][j], i, j);
                }
        }
        sort(s1.rbegin(), s1.rend());
        vector<ll> col(n, m - 1);
        vector<vector<pair<ll, ll>>> del;
        vector<ll> ans(1, 0);
        for (auto[_, x, y] : s1) {
                if (col[x] < y) {
                        continue;
                }
                del.emplace_back(0);
                for (ll j = x; j < n; j++) {
                        if (col[j] < y) {
                                break;
                        }
                        while (col[j] >= y) {
                                del.back().emplace_back(j, col[j]);
                                assign_max(ma, arr[j][col[j]]);
                                assign_min(mi, arr[j][col[j]]);
                                col[j]--;
                        }
                }
                ans.push_back(ma - mi);
        }
        mi = INF32;
        ma = 0;
        ll na = ans.back();
        while (!del.empty()) {
                for (auto[x, y] : del.back()) {
                        assign_max(ma, arr[x][y]);
                        assign_min(mi, arr[x][y]);
                }
                del.pop_back();
                ans.pop_back();
                assign_min(na, max(ans.back(), ma - mi));
        }
        return na;
}

void solve() {
        ll n, m;
        cin >> n >> m;
        vector<vector<ll>> arr(n, vector<ll>(m));
        for (ll i = 0; i < n; i++) {
                for (ll j = 0; j < m; j++) {
                        cin >> arr[i][j];
                }
        }
        ll ans = INF32;
        for (ll i = 0; i < 2; i++) {
                reverse(arr.begin(), arr.end());
                for (ll j = 0; j < 2; j++) {
                        for (auto& k : arr) {
                                reverse(k.begin(), k.end());
                        }
                        assign_min(ans, sol(n, m, arr));
                }
        }
        cout << ans << '\n';
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message

joioi.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   12 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:127:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:128:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 20 ms 2232 KB Output is correct
17 Correct 16 ms 1792 KB Output is correct
18 Correct 20 ms 2052 KB Output is correct
19 Correct 16 ms 2048 KB Output is correct
20 Correct 15 ms 1904 KB Output is correct
21 Correct 16 ms 2072 KB Output is correct
22 Correct 15 ms 1792 KB Output is correct
23 Correct 16 ms 1824 KB Output is correct
24 Correct 17 ms 1832 KB Output is correct
25 Correct 16 ms 1788 KB Output is correct
26 Correct 17 ms 2216 KB Output is correct
27 Correct 16 ms 1964 KB Output is correct
28 Correct 17 ms 1920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 20 ms 2232 KB Output is correct
17 Correct 16 ms 1792 KB Output is correct
18 Correct 20 ms 2052 KB Output is correct
19 Correct 16 ms 2048 KB Output is correct
20 Correct 15 ms 1904 KB Output is correct
21 Correct 16 ms 2072 KB Output is correct
22 Correct 15 ms 1792 KB Output is correct
23 Correct 16 ms 1824 KB Output is correct
24 Correct 17 ms 1832 KB Output is correct
25 Correct 16 ms 1788 KB Output is correct
26 Correct 17 ms 2216 KB Output is correct
27 Correct 16 ms 1964 KB Output is correct
28 Correct 17 ms 1920 KB Output is correct
29 Correct 2128 ms 111672 KB Output is correct
30 Correct 1996 ms 137680 KB Output is correct
31 Correct 2156 ms 150160 KB Output is correct
32 Correct 2152 ms 144628 KB Output is correct
33 Correct 1845 ms 127424 KB Output is correct
34 Correct 2147 ms 148728 KB Output is correct
35 Correct 1969 ms 183788 KB Output is correct
36 Correct 1681 ms 147848 KB Output is correct
37 Correct 1985 ms 188288 KB Output is correct