Submission #518018

#	Time	Username	Problem	Language	Result	Execution time	Memory
518018		Be_dos	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	1087 ms	28456 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);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, m;
    std::cin >> n >> m;

    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];
    }

    std::pair<int32_t, int32_t>* order = new std::pair<int32_t, int32_t>[n * m];
    for(int32_t i = 0; i < n; i++)
        for(int32_t j = 0; j < m; j++)
            order[i * m + j] = {i, j};
    std::sort(order, order + n * m, [&](std::pair<int32_t, int32_t> p1, std::pair<int32_t, int32_t> p2) {
        return arr[p1.first][p1.second] < arr[p2.first][p2.second];
    });

    int32_t ans = 0;
    Segtree segtree_lt(n, m), segtree_lb(n, m), 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 - segtree_lt.get_min(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 - segtree_lb.get_min(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_lt.set(order[i].first, order[i].second, arr[order[i].first][order[i].second] - order[i].first - order[i].second);
        segtree_lb.set(n - order[i].first - 1, order[i].second, arr[order[i].first][order[i].second] + order[i].first - 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;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40