Editorial for Max's Anger Contest Series 2 P3 - Array Anger
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
For each query, brute force the first index that satisfies it by maintaining the current sum up to a certain index and then moving the pointer.
Time Complexity:
Subtask 2
For each query, binary search for the first index that satisfies it and query with a prefix sum array to query the sum.
Time Complexity:
Note that it is possible to replace the prefix sum array with most static interval query data structures (e.g. sparse table, segment tree, or Fenwick tree).
Additionally, the author believes that distinguishing between a log factor (e.g. segment tree vs. prefix sum array) is unfair to competitors and intentionally set a high time limit to prevent this distinction.
Comments