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

Правка en2, от ekzhang, 2016-06-30 04:06:26

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.me/contest/375/submission/18813131

Second Submission: http://codeforces.me/contest/375/submission/18813311

Diff: https://www.diffchecker.com/nhyeayxp

Thank you very much!

Теги mo, tree, inorder, fenwick

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ekzhang 2016-06-30 04:06:26 4 fix spacing on links
en1 Английский ekzhang 2016-06-30 04:06:03 1067 Initial revision (published)