Submission #518137

#	Time	Username	Problem	Language	Result	Execution time	Memory
518137		Be_dos	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	1098 ms	43984 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 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