oj.uz

Submission #518137

# Submission time Handle Problem Language Result Execution time Memory
518137 2022-01-23T08:45:19 Z Be_dos Maxcomp (info1cup18_maxcomp) C++17
60 / 100
 500 ms 43984 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 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 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 1 ms 844 KB Output is correct

Subtask #3
30.0 / 30.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 844 KB Output is correct
16 Correct 2 ms 844 KB Output is correct
17 Correct 2 ms 844 KB Output is correct
18 Execution timed out 1098 ms 43984 KB Time limit exceeded
19 Halted 0 ms 0 KB -