oj.uz

Submission #518258

# Submission time Handle Problem Language Result Execution time Memory
518258 2022-01-23T09:13:28 Z Be_dos Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 273 ms 52672 KB 
#include <iostream>
    #include <cmath>
    #include <cctype>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <deque>
    #include <stack>
    #include <unordered_set>
    #include <sstream>
    #include <cstring>
    #include <iomanip>
    #include <queue>
    #include <unordered_map>
    #include <random>
    #include <cfloat>
    #include <chrono>
    #include <bitset>
    #include <complex>
    #include <immintrin.h>
    #include <cassert>
     
    struct Segtree {
    int32_t** bit;
    int32_t n_, m_;
     
    Segtree(int32_t n, int32_t m) {
        n_ = n;
        m_ = m;
        bit = new int32_t*[n];
        for(int32_t i = 0; i < n; i++) {
            bit[i] = new int32_t[m];
            for(int32_t j = 0; j < m; j++)
                bit[i][j] = 2'000'000'000;
        }
    }
     
    int32_t get_min(int32_t right1, int32_t right2) {
        int32_t res = 2'000'000'000;
        for(int32_t i = right1 - 1; i >= 0; i = (i & (i + 1)) - 1)
            for(int32_t j = right2 - 1; j >= 0; j = (j & (j + 1)) - 1)
                res = std::min(res, bit[i][j]);
            return res;
    }
     
    void set(int32_t ind1, int32_t ind2, int32_t val) {
        for(int32_t i = ind1; i < n_; i |= (i + 1))
            for(int32_t j = ind2; j < m_; j |= (j + 1))
                bit[i][j] = std::min(bit[i][j], val);
    }
};
     
struct OrderEntry {
    int32_t first, second;
    int32_t val;
     
    bool operator<(OrderEntry& other) {
        return val < other.val;
    }
};
     
OrderEntry* tmp;
#define BITS 16
void radix_sort(OrderEntry* arr, int32_t n, int32_t shift) {
    int32_t* cnt = new int32_t[(1 << BITS) + 1];
    for(int32_t i = 0; i < (1 << BITS) + 1; i++)
        cnt[i] = 0;
    for(int32_t i = 0; i < n; i++)
        cnt[((arr[i].val >> (shift * BITS)) & ((1 << BITS) - 1)) + 1]++;
    for(int32_t i = 1; i < (1 << BITS) + 1; i++)
        cnt[i] += cnt[i - 1];
    for(int32_t i = 0; i < n; i++)
        tmp[cnt[(arr[i].val >> (shift * BITS)) & ((1 << BITS) - 1)]++] = arr[i];
    for(int32_t i = 0; i < n; i++)
        arr[i] = tmp[i];
}
     
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
     
    int32_t n, m;
    std::cin >> n >> m;
     
    //std::mt19937 rng;
    int32_t** arr = new int32_t*[n];
    for(int32_t i = 0; i < n; i++) {
        arr[i] = new int32_t[m];
        for(int32_t j = 0; j < m; j++)
            std::cin >> arr[i][j];
        //arr[i][j] = rng() % 1'000'000'000 + 1;
    }
     
    OrderEntry* order = new OrderEntry[n * m];
    for(int32_t i = 0; i < n; i++)
        for(int32_t j = 0; j < m; j++)
            order[i * m + j] = {i, j, arr[i][j]};
    tmp = new OrderEntry[n * m];
    radix_sort(order, n * m, 0);
    radix_sort(order, n * m, 1);

    int32_t** pref_min_lt = new int32_t*[n + 1];
    for(int32_t i = 0; i < n + 1; i++) {
        pref_min_lt[i] = new int32_t[m + 1];
        for(int32_t j = 0; j <= m; j++)
            if(i == 0 || j == 0)
                pref_min_lt[i][j] = 2'000'000'000;
            else {
                pref_min_lt[i][j] = std::min(pref_min_lt[i - 1][j], pref_min_lt[i][j - 1]);
                pref_min_lt[i][j] = std::min(pref_min_lt[i][j], arr[i - 1][j - 1] - (i - 1) - (j - 1));
            }
    }
    int32_t** pref_min_lb = new int32_t*[n + 1];
    for(int32_t i = 0; i < n + 1; i++) {
        pref_min_lb[i] = new int32_t[m + 1];
        for(int32_t j = 0; j <= m; j++)
            if(i == 0 || j == 0)
                pref_min_lb[i][j] = 2'000'000'000;
            else {
                pref_min_lb[i][j] = std::min(pref_min_lb[i - 1][j], pref_min_lb[i][j - 1]);
                pref_min_lb[i][j] = std::min(pref_min_lb[i][j], arr[n - i][j - 1] + (n - i) - (j - 1));
            }
    }
    int32_t** pref_min_rt = new int32_t*[n + 1];
    for(int32_t i = 0; i < n + 1; i++) {
        pref_min_rt[i] = new int32_t[m + 1];
        for(int32_t j = 0; j <= m; j++)
            if(i == 0 || j == 0)
                pref_min_rt[i][j] = 2'000'000'000;
            else {
                pref_min_rt[i][j] = std::min(pref_min_rt[i - 1][j], pref_min_rt[i][j - 1]);
                pref_min_rt[i][j] = std::min(pref_min_rt[i][j], arr[i - 1][m - j] - (i - 1) + (m - j));
            }
    }
    int32_t** pref_min_rb = new int32_t*[n + 1];
    for(int32_t i = 0; i < n + 1; i++) {
        pref_min_rb[i] = new int32_t[m + 1];
        for(int32_t j = 0; j <= m; j++)
            if(i == 0 || j == 0)
                pref_min_rb[i][j] = 2'000'000'000;
            else {
                pref_min_rb[i][j] = std::min(pref_min_rb[i - 1][j], pref_min_rb[i][j - 1]);
                pref_min_rb[i][j] = std::min(pref_min_rb[i][j], arr[n - i][m - j] + (n - i) + (m - j));
            }
    }

    int32_t ans = 0;
    for(int32_t i = 0; i < n * m; i++) {
        ans = std::max(ans, arr[order[i].first][order[i].second] - order[i].first - order[i].second - pref_min_lt[order[i].first + 1][order[i].second + 1]);
        ans = std::max(ans, arr[order[i].first][order[i].second] + order[i].first - order[i].second - pref_min_lb[n - order[i].first][order[i].second + 1]);
        ans = std::max(ans, arr[order[i].first][order[i].second] - order[i].first + order[i].second - pref_min_rt[order[i].first + 1][m - order[i].second]);
        ans = std::max(ans, arr[order[i].first][order[i].second] + order[i].first + order[i].second - pref_min_rb[n - order[i].first][m - order[i].second]);
    }

    std::cout << ans - 1;
    return 0;
}

Compilation message

maxcomp.cpp: In member function 'int32_t Segtree::get_min(int32_t, int32_t)':
maxcomp.cpp:41:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |         for(int32_t i = right1 - 1; i >= 0; i = (i & (i + 1)) - 1)
      |         ^~~
maxcomp.cpp:44:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 |             return res;
      |             ^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 984 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 984 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 2 ms 964 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Correct 2 ms 1024 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 984 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 964 KB Output is correct
14 Correct 2 ms 972 KB Output is correct
15 Correct 2 ms 972 KB Output is correct
16 Correct 2 ms 972 KB Output is correct
17 Correct 2 ms 1024 KB Output is correct
18 Correct 273 ms 44356 KB Output is correct
19 Correct 243 ms 52672 KB Output is correct
20 Correct 209 ms 50092 KB Output is correct
21 Correct 266 ms 52512 KB Output is correct
22 Correct 243 ms 52552 KB Output is correct
23 Correct 233 ms 52544 KB Output is correct
24 Correct 188 ms 51268 KB Output is correct