Разбор добавил Игорь Беляев

Для решения данной задачи необходимо реализовать принцип сортировки слиянием. Первый массив будет состоять из квадратов чисел, второй из кубов. Хранить массивы не требуется. Достаточно на каждом шаге знать крайние элементы, которые участвуют в слиянии. Давайте оценим максимальные значения двух массивов. Для первого это 10^14, для второго 10^21. Но не надо думать, что придется реализовывать длинную арифметику. Максимальный индекс в конечном массиве не превосходит 10^7, а сами элементы будут состоять из элементов первого массива, "разбавленные" элементами второго массива. Поэтому можно с уверенностью сказать, что элементов больше, чем 10^14 в финальном массиве нет. Отсюда вывод: в качестве типа данных для элементов массивов выбираем long long, а не int, как может показаться с первого раза.