Hello everyone! I am new to competitive coding and asking a rookie query in a blog for the first time so apologies in advance if anything is not according to norms.
I was solving this problem today 1284B - New Year and Ascent Sequence . Here is the editorial. Idea behind my solution is almost as in editorial. The issue is that my submission with custom function for upper_bound got tle verdict but when I used built in function for the same it got accepted.
I used the concept of binary search in my function so the overall complexity is still O(nlogn) which should get accepted(according to me).
My code for upper_bound func
86441251 is the submission which got tle. 86412015 is the submission which got accepted.
Thanks in advance!
When you are calling the function bs with the vector maxv as a prameter, the vector is copied every time you call the function, so the copying takes time O(size of vector), which should be the cause of the TLE. To avoid that, simply pass the vector by reference ( & maxv) which will not make a copy