Getting TLE in subtask 11…HELP!!!

question-link text

solution-link text

here N<=10^5.you should do that in O(N),but your logic is O(N^2)

oh!!!my mistake

You can simple use a formula to overcome TLE.

Lets say, we encounter an array -

{4,3,2,5,1,2,3,4,2,3}

Lets say, we are checking from index 4 (0-based indexing). The subarray is {1,2,3,4}

Now, how many non decreasing sub array can it have IF the block is strictly non-decreasing?

The answer is 4*(4+1)/2

The sub-arrays are-

1,2,3,4,{1,2},{2,3},{3,4},{1,2,3},{2,3,4},{1,2,3,4}

This allows you to skip the entire block and goto next one. Meaning, now you can straightaway start checking from index 8.

You can easily derive it if you use pen and paper. Here is my solution which uses it- https://www.codechef.com/viewsolution/14289006