After TLE'ing this problem in the contest I've been unable to come up with a satisfactory explanation as for why it does so. The mystery is why does my solution behave so much worse on case 65 than any of the other previous max sized cases. Since I cannot clearly see a reason why I feel it's possible this could happen again. I'm not looking for suggestions on how to make my code faster.
My solution is listed at http://mirror.codeforces.com/contest/498/submission/9250377
I've noticed other solutions that did manage to pass using essentially the same algorithm are also significantly slower on case 65 than any of the other cases. For example http://mirror.codeforces.com/contest/498/submission/9251777
Link to problem — http://mirror.codeforces.com/problemset/problem/498/B