TLE in SPOJ problem D-QUERY with segment tree

Revision en1, by svineet, 2017-02-16 13:36:54

Hi,

Problem
My solution

I made a segment tree with a slight modification to the merge function from merge sort. The recurrence should come to:

T(n) = 2T(n / 2) + O(n)

Which should be O(n lg n), for the initial building part. For each query it would take O(lg n) right? Why is this timing out? I made a huge test case and it kept running for like a minute. I tried fast i/o, tried to store results and output later, and converted the vector to list but nothing worked.

Is my analysis wrong? How do I make it faster? Please help.

Tags #c++, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English svineet 2017-02-16 13:36:54 674 Initial revision (published)