We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Solved using Sparse tables, which are nlogn in building and space requirements, but allow o(n) time per each query length. They can be used, because the array is immutable in this problem and seem much better than segment trees. Worst case result is 0.02s in C++.
In contrast, the Code from Editorial (Problem Setter's) is giving 0.17s worst case.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queries with Fixed Length
You are viewing a single comment's thread. Return to all comments →
Wasn't sure how to apply queues to this problem.
Solved using Sparse tables, which are nlogn in building and space requirements, but allow o(n) time per each query length. They can be used, because the array is immutable in this problem and seem much better than segment trees. Worst case result is 0.02s in C++.
In contrast, the Code from Editorial (Problem Setter's) is giving 0.17s worst case.