Mysterious bottleneck for wxhtzdy ORO Tree

Правка en1, от dino_merlin, 2024-03-04 16:49:34

A while back I solved the problem wxhtzdy ORO Tree and I had some problems with the time limit, but I managed to squeeze it below the 5s mark by, instead of calculating for each important node the value of the function, calculating the contribution of each important node to the original answer (link to AC submission). I thought that calculating the value of the function each time has a large constant factor and it turned out to be true. However, a few days ago I was helping a friend solve the problem and noticed that his code, with the same idea that would not work for me (link to the TLE submission), passed comfortably. Now, I am confused as to why my code is so inefficent. Could anyone help me point out the bottlenecks in my code?

Теги implementation, tree, binary lifting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский dino_merlin 2024-03-04 16:49:34 953 Initial revision (published)