Take a look at these two submissions made by me:
Result: AC (for both tasks)
Result: TLE (for second
task)
Note that the only difference between the two is that the 2nd one contains two lines extra;
#define min(a,b) ((a < b)?a:b)
#define max(a,b) ((a > b)?a:b)
Why is the 1st one AC but 2nd TLE!? o_O
Am I overlooking something that is insanely obvious?
Please Help!
Most probably this is the line that makes difference:
return min (queryUtil ( 2 * i + 1, a, mid, l, r ), queryUtil ( 2 * i + 2, mid + 1, b, l, r ) );
Your min macro makes additional function calls thus increasing the time which probably lead to TLE for 2nd subtask.
You should store those values in some temporary variables and then use your min(macro) or just use the default min function.
Yes one of the function calls will be done twice. It would be far better to use the built in function or convert your macro to a function. The preprocessor converts your macro to the following for the above example:
return ((queryUtil ( 2 * i + 1, a, mid, l, r ) < queryUtil ( 2 * i + 2, mid + 1, b, l, r )) ? queryUtil ( 2 * i + 1, a, mid, l, r ) : queryUtil ( 2 * i + 2, mid + 1, b, l, r );
Aha! That completely slipped out of my mind! Thanks.