Just completed this after around 2 weeks of attempts, I used @paulpach's hint and that jump-started me for sure, but, like many of you, I was still timing out.

Because there's so much going on behind the scenes in these functional languages (namely haskell as that's what I used), it's hard to tell what the actual slowing factor is, so to maybe help a few of you I'll give a tip.

The tip is: if you have a slow yet working solution following @paulpach's hint, then try and focus on simplifying your structures. Try and simplify things down until you have as much personal control as possible over operations on those structures. Optimizing the smaller operations as much as possible could mean the difference between 40 seconds and 4 seconds just by the fact that they're used so much during the longer test cases.

Hope this helps (and also hope this doesn't help too much that I spoiled it)