Since this problem is set for segment trees, Kadane’s algorithm failed. So I looked up segment trees and got the gist of it. I followed this for learning the basics:
After trying few times, I got my code working, but got a WA for final test caes, so I googled up the concept of maximum subarray and managed to get it working, but now my implementation times out, even with optimized IO (beyond scanf and printf, using one of those fancy templates available online)
I decided to remove everything, including vectors, and deal purely with arrays and scanf/printfs and I still get a time out. Either the time limit is really strict or the code doesn’t work as I think it should and maybe gets stuck.
Here is my final implementation using arrays: