Piling Up with Python
The algorithm is actually pretty efficient, so congrats for that.

The first thing that I'd like to suggest is moving the logic outside the main check. In python, it's fairly common (and IMO more readable) to have your structure like this:

imports

def pile_algo(*args, **kwargs):
    """Docstring here"""
    # your code


def main():
    """Docstring here"""
    # process pile_algo

if __name__ == '__main__':
    main()


Of course, the main() is optional if you already have all the logic inside pile_algo().

Even if I said the algorithm is good, we can improve the way you're doing things.

You're not using num_cubes variable, so you can remove it (int(input().strip()) it's enough). Moving forward, neither use of strip() or list() or map() is necessary in your:

cube_sidelengths = list(map(int, map(str.strip, input().strip().split())))


You can rewrite that as:

cube_sidelengths = [int(x) for x in input().split()]




Apart from that, I don't have any other reasons to think about using deque. If it works, it works. And apparently works better enough to get over it.

Though, of course, I would also ask: Is it too slow right now? Most of the times, the aim of a programming challenge is both getting familiar with a specific library/module and improve your algorithms skills. You said:


  It would be possible to use a deque here but that felt like overkill -
  because pop and popLeft are O(1) but just keeping the indices and
  accessing a list is also O(1) so it wouldn't even provide better
  asymptotic behavior.


Well, it would provide a worse asymptotic behavior? Just start writing a deque-based solution and see what improvements might that bring. I can think of a few right now:


the code will be more comprehensive because of deque's already builtin methods which might do what you manually did (pop, etc..)
talking about efficiency, Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.


From the docs:


  Deques support thread-safe, memory efficient appends and pops from
  either side of the deque with approximately the same O(1) performance
  in either direction.
  
  Though list objects support similar operations, they are optimized for
  fast fixed-length operations and incur O(n) memory movement costs for
  pop(0) and insert(0, v) operations which change both the size and
  position of the underlying data representation.




This might look more of a theory answer, and might not specifically answer your question, but I just wanted to highlight a couple of things out.