クロッシング問題の回答。計測位置間違えてそうなことに提出後に気づいた。 普通にマージソートで転倒数求めてます。Rubyでやったら配列の確保とかに時間かかってるっぽかったので、修正も面倒だしC++で書き直しました。途中までin-placeなマージソートの実装追い求めてましたが、色々頭が混乱してきたので最終的に至って普通のマージソートになりました。

solve.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdint>

std::vector<int> buf;
std::uintmax_t answer = 0;

void merge(int *arr, size_t arr1_size, size_t arr2_size)
{
	using namespace std;
	copy(arr, arr + arr1_size + arr2_size, buf.begin());

	int *arr1 = &buf[0];
	int *arr1_end = arr1 + arr1_size;

	int *arr2 = arr1_end;
	int *arr2_end = arr2 + arr2_size;

	for (; arr1 < arr1_end && arr2 < arr2_end; ++arr)
	{
		if (*arr1 < *arr2)
		{
			*arr = *arr1;
			arr1 += 1;
		} else
		{
			*arr = *arr2;
			arr2 += 1;
			answer += arr1_end - arr1;
		}
	}

	for (; arr1 < arr1_end; ++arr, ++arr1)
	{
		*arr = *arr1;
	}

	for (; arr2 < arr2_end; ++arr, ++arr2)
	{
		*arr = *arr2;
	}
}

void sort(int *arr, size_t size)
{
	if (size <= 1) return;

	size_t half_size = size / 2;
	
	int *arr1 = arr;
	size_t arr1_size = half_size;
	sort(arr1, arr1_size);

	int *arr2 = arr + half_size;
	size_t arr2_size = size - half_size;
	sort(arr2, arr2_size);

	merge(arr, arr1_size, arr2_size);
}

int main(int argc, char *argv[])
{
	std::vector<int> perm;
	perm.reserve(524288);
	buf.reserve(524288);

	for (;;)
	{
		int num;
		std::cin >> num;

		if (std::cin.eof()) break;
		perm.push_back(num);
	}

	namespace chrono = std::chrono;

	auto begin = chrono::system_clock::now();
	sort(&perm[0], perm.size());
	auto end   = chrono::system_clock::now();

	auto wall_time =
		chrono::duration_cast<chrono::second>(end - begin);
	std::cout
		<< answer << "," << wall_time.count() << std::endl
		<< "ENV: C++" << std::endl;
	
	return 0;
}