Hello! I've been trying to solve the problems from 2024-2025 ICPC Latin American Regional Programming Contest. I think I got the solution to problem C, 105505C - Cindy's Christmas Challenge. This is my latest solution 298605401. I'm getting WA on test 5 and I have no idea why.

What I basically did was figure out that to turn the substring [L,U] into R red balls, I need max(R, U-L+1)-min(R,r), where r is the amount of red balls in the substring. Now I split the interval into two, [L,I] to turn into R red balls and [I+1,U] to turn into B blue balls. Making two preffix arrays r and b to easily get the amount of blue and red balls, I have that I need N=max(R, I-L+1)+max(B,U-I)-min(R, r[I]-r[L-1])-min(B,b[U]-b[I]). There are only 9 possible different ways to combine the terms inside the maxes/mins (given that, for example, if R is bigger than the interval, then the amounts of red balls must also be smaller than R). I separated each of these 9 functions into a part that depends only on I, and one that only depends on R,B,L and U.

Now for each of the 9 functions that depend on I, I built sparse tables over the whole original array to make RMQs. Then for each query I calculate the corresponding constants that I have to add. Now, there are at most 4 points on which the whole function changes behaviour: when R=I-L+1, B=U-I, R = r[I]-r[L-1] and B=b[u]-b[I]. The first two are given, I found the last two with binary search. Now I take the intersection of these 5 intervals with [L,U], find which of the 9 functions applies there, and I do a RMQ on each subinterval to find the optimal splitting point and the minimum amount of moves needed.

The problem is, I get a wrong answer on test 5 and I don't know why. I've tried all corner cases I thought of and I can't find what's wrong. The editorial posted on the contest and the video editorial made by elsantodel90 both suggest the same approach I've taken.