Submission #518253

#	Time	Username	Problem	Language	Result	Execution time	Memory
518253		Be_dos	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	750 ms	52504 KiB

maxcomp

#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 ans = 0;
    Segtree segtree_rt(n, m), segtree_rb(n, m);
    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 - segtree_rt.get_min(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 - segtree_rb.get_min(n - order[i].first, m - order[i].second));

        segtree_rt.set(order[i].first, m - order[i].second - 1, arr[order[i].first][order[i].second] - order[i].first + order[i].second);
        segtree_rb.set(n - order[i].first - 1, m - order[i].second - 1, arr[order[i].first][order[i].second] + order[i].first + order[i].second);
    }

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

Compilation message (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40