My Ternary search solution gives the same output as the Setter’s solution code and your AC submission on 1000s of randomized test cases yet it’s giving WA on submission for some of the testcases
Is it possible to create this difference array without segment tree? The normal difference array creating method doesnt work for state A and C, since the updates differ by 4.
Whats state A,C? normal difference array creating method would be having 2 loops from y1 and y2 and it would take at worse O(n) time for EACH segment. Thats why we gotta use range update
Ya thats what I meant. For same updates like {9, 9, 9}, I used normal update (add X to L and sub x from R+1) in O(1) but had no idea how to update for variable updates like {1, 5}.
Thanks for providing an edge case, it’s true that ternary search doesn’t work because the distribution of the total time taken by speeding up y=m from m=1 to 100 in your test case isn’t convex. It’s something like 8 10 10 10 .... 10 9 10 ...... 10 9 10 .... where m=1 is the minima.
Although the reason I was facing WA was because I had set low constraints in my random test case generator script and I didn’t notice that I had initialized the result with INT_MAX instead of LLONG_MAX Changing that gave me AC so it seems that the test cases are weak.