maybe you should write 1LL instead of 1ll. It might be easier to clarify or check for typo <(")

valid crashout

Peak extension fr

Can i join:P

My submission 325661310 might be valid with this problem, cause this code AC with the same problem with the same constrain(1793C - Dora and Search)

I think the priority queue not gonna make it O(n) casuse on 1 operation, an priority queue takes O(logn) to compute.

The valid O(n) solution might be using 4 monotonic stack for next/previous min/max(precompute in O(n) and remove element from both end like usual. But it's an absurd amount of coding for a problem with constrain n < 2e5. Maybe if is was limit on number of steps you can take, or the time constrain need strictly O(kn) with k <= 10 and n is large enough. I'll use this method.

Personaly, i'll stick with using multi_set because it will make my code shorter, easier to code and understand.

My personal though process:

1. If we trimmed an element which is not the min_val nor the max_val from the subarray, then nothing will happened except the length of the subarray decrease by 1 -> bad bad:D
2. If we trimmed an element which is local min/max val from the subarray that on the right/left end of the array, we won't lose any valid solution.

And i also think that this could also work with an subsequence from the array, cause:

1. If we remove an min/max val in the middle of the subsequence(not the right/left end), it won't change an invalid subsequence into a valid subsequence cause the right/left end remain the same.

So it's still a bad thing to remove element from middle of the subsequence. I think this will work, correct me if i'm wrong pls:D

I think you could use a multi_set to store all the value from the array, and remove either value from both end if is the min or max val from the subarray/subsequence.

Repeat until it's valid. The time complexity is O(nlogn):D

Thanks bro, u too:D

Good luck have fun guys:D

i_love_huyhau6a2 will win IOI 2025!!!

glhf guys :Đ ++ratings