I tried solving the problem using segment trees but I am getting runtime error on submission. My code is available here. I analyzed all the array sizes but they seem correct. Any ideas as to why it is producing runtime error?
Update
The problem with solution is size of the array tree. On careful inspection it can be seen that the maximum index of the array accessible is 2*(2*n+1) where n is the maximum size of the input. To prevent that we can either increase the size of the array to 4*n or put a check that it never exceeeds the maximum limit size.