Hi USACO Forum!

https://codeforces.com/gym/104114/problem/N

I solved this problem but I am having trouble understanding the alternate solution in the editorial

“Note: Alternatively, one may observe that the maximum value in s will never change. Therefore, one may

propagate the constraints given by the maximum value left and right, erase it, and repeat. By using a

priority queue to simulate the process, one can achieve O(n log n) complexity.”

How does this even work as the maximum value will constantly be changing after you ignore the previously used maximum values?

For example, if you have the salt values in order 29. 73, 30, 87, then after the first move the set will be

29, 73, 77, 87 and now the previous “30” is the new maximum value, forcing you to sort every time…