Official Editorial (C++)

Explanation

Essentially, the solution is to use nested loops to iterate through the columns input matrix, then calculate the sum of each column, and sort the elements of each column in non-descending order. Then calculate the absolute difference between the sum of the column and a running sum of the sorted elements. This difference is multiplied by the number of elements that come before it in the sorted order to obtain the contribution of that element to the final answer. The contributions of all elements in a column are then summed up to obtain the final answer for that column, and this process is repeated for all columns.

The idea behind this approach is that the current element is being used as a representative of all the elements in the column that are smaller than it. Therefore, the difference between the sum of all elements and the sum of all elements before the current element is the sum of all the elements that are greater than the current element. This difference is then multiplied by the number of rows minus one minus the number of rows before the current element to obtain the total number of inversions.

Implementation

Time Complexity: $\mathcal{O}(MN \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> a(n, vector<int>(m));
		for (int i = 0; i < n; i++) {

Copy
from collections import defaultdict

for _ in range(int(input())):
	deck_num, card_num = map(int, input().split())
	matrix = []
	for _ in range(deck_num):
		matrix.append(list(map(int, input().split())))

	# Group columns using a dictionary
	hashmap = defaultdict(list)

Copy
import java.io.*;
import java.util.*;

public class PlayingInCasino {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {