Hi everyone, I have been working on what originally seemed to me both in the contest and even now a really simple problem, but I haven't been able to solve it even after looking at someone else's program. The problem is making me angry enough to tank the grey downvotes since I really have no clue what else I can fix about my program.
Here is my submission: https://codeforces.me/contest/1846/submission/214439016 And here is the person I am looking at's submission: https://codeforces.me/contest/1846/submission/212618879
Can someone explain to me what I am missing? I think it has something to do with passing or creating arrays as far as I can tell. If I change my array of positions "res" to a 2d ArrayList and pass around rows of it, I time out on an earlier test case. Can someone please take a look and let me know what I am missing?
Also, just looking at the case I fail on, it seems like it has something to do with sorting a singular really long array, but the math works out to less than 10^8 so I must be missing something big.
Thank you in advance
Update: Turns out the test cases are just really hostile to java. Check out this amazing blog to avoid these pitfalls: https://codeforces.me/blog/entry/116603
TLDR: Quicksort on primitives can be hacked, fix with ruffle sort or using Integer/Long wrapper classes