Помогите сократить время работы кода при максимальных значениях

Question

#include <iostream>
#include <vector>
#include <climits> 

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    int arr[20][10000];

    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> arr[i][j];
        }
    }
    int otjm = 0;
 
    for (int i = 0; i < k; ++i) {
       
        for (int j = 1; j < n; ++j) {
            int count = 0;
            for (int m = 0; m < j; ++m) {
                if (arr[i][m] > arr[i][j]) {
                    count++;
                }
            }
            otjm += count;
        }
    }

    cout << otjm;
   

    return 0;
}

(k - количество строк до 20, n - столбцов до 10000)

суть в программы в том, что для каждого числа каждой строки нужно найти количество чисел слева, больше текущего и сложить все значения. выдаёт ошибку Time limit exceeded для максимальных значений. Как можно оптимизировать это? пример теста:

5 2

1 5 2 4 3

2 3 1 5 4

вывод: 7

Answer 1

Время пришло написать подсчёт инверсий за NlogN через сортировку слиянием. Это обычный merge_sort с одной особенностью: каждый раз когда элемент из второго массива "обгоняет" элементы из первого массива и вставляется в результат, количество "обогнанных" элементов накапливается в счётчике инверсий. Можно показать что в итоге получится суммарное количество инверсий для всех элементов массива.

#include <iostream>
#include <vector>

using Array = std::vector<int>;

auto merge(const Array &a, const Array &b, Array &c) {
    size_t n_invs = 0;
    auto m = a.size();
    decltype(m) i = 0;
    auto n = b.size();
    decltype(n) j = 0;
    decltype(c.size()) k = 0;
    while (i < m && j < n) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
            n_invs += m - i;
        }
    }
    for (; i < m; ++i) {
        c[k++] = a[i];
    }
    for (; j < n; ++j) {
        c[k++] = b[j];
    }
    return n_invs;
}

size_t merge_sort(Array &a) {
    auto i = a.size() >> 1;
    if (i == 0) {
        return 0;
    }
    Array lo(a.begin(), a.begin() + i         );
    Array hi(           a.begin() + i, a.end());
    auto n_invs = merge_sort(lo) + merge_sort(hi);
    return n_invs + merge(lo, hi, a);
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;
    Array line(n);

    size_t answer = 0;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> line[j];
        }
        answer += merge_sort(line);
    }
    std::cout << answer << '\n';
}

БЛОГ НА HUSL

Помогите сократить время работы кода при максимальных значениях

Ответы (1 шт):