D. Array Restoration Getting TLE

Problem MySol .

My Approach -
Answer is no if there exist i < j in range minIndx of j to maxIdx of j.
For This I have used segment tree.
Time Complexity according to me - O((n+q)*logn) Which Should pass TL.

what is your approach?? how you have used segment tree?
i think solution possible without segment tree .

Can you elaborate your condition for no solution. According to me it was that if there exist i<j<k such that a[i] = a[k] and a[j] is smaller then answer is no. Can you briefly explain your approach.

Yes, I’m using this condition. Along with checking if no q exist or not in given array. Or if it can be inserted or not.

1 Like

I’m using segment tree. But I have not inserted 0 in tree. Instead using INF. And for given range l,r. I’m returning smallest no in this range. And using condition @vishesh345 's answer.

Thank you friends. I have got AC on 33rd submission xD. I just removed one linear loop for inserting q by using some more variables. And removed handling of special case of 1.