Help! Attempting to optimize Mo's Algorithm leads to TLE on case 5?!

Revision en1, by ekzhang, 2016-06-30 04:06:03

Hi, I am currently trying an O(n(sqrt n)(lg n)) to problem 375D using Mo's Algorithm and a Fenwick Tree. My initial solution got a time limit exceeded on test case 53, so I tried to optimize it.

To optimize, I made a couple of changes to my check() function, that is called every time the Mo's Algorithm window is slid 1 tree node. I was thinking that this would make the algorithm run faster since check is the part that is run the most (n^1.5 lg n times).

My second submission didn't end up working. In fact, somehow, my new submission got TLE on test case 5, which the previous code could solve in 150ms!

Can someone help me figure out what could've happened that would make this attempted optimization run 10x slower?

Original Submission: http://codeforces.com/contest/375/submission/18813131 Second Submission: http://codeforces.com/contest/375/submission/18813311 Diff: https://www.diffchecker.com/nhyeayxp

Thank you very much!

Tags mo, tree, inorder, fenwick

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ekzhang 2016-06-30 04:06:26 4 fix spacing on links
en1 English ekzhang 2016-06-30 04:06:03 1067 Initial revision (published)