CSUBQ of NOV17 -getting tle with the 2 Segment Trees approach in Java

Here is my code which got only 52 points

I am not able to understand why am I getting TLE.
I am also using custom fast input/output classes for Java.

1 Like

Go iterative instead of recursive- recursive is very expensive in Python and JAVA, unlike C++.

2 Likes

Unlike C++
Does this mean in C++ it is good to do recursively??

Its not as penalizing as in JAVA or python- where even recursion depth of {10}^{6} throws runtime error.

Hi @adzo261, I made a submission using recursive segment tree like you did and got TLE: 16294122.
So I thought probably @vijju123 is right and changed my solution to use iterative segment tree operations but I still got TLE: 16294816.
So I decided to get rid of all unnecessary object creations by using an update procedure rather than using new objects, and I barely made it: 16294847.

I think the time limit for Java should have been relaxed further for this problem. Ordinary unoptimized recursive segment tree easily gets AC in C++.

1 Like

However we don’t normally need to worry about recursion depth with segment trees because it is at most \lceil\log_2(N)\rceil

1 Like

Some things are way too costly even for a 2x time limit. I was quite sure that iterative would pass easily :confused: