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.
First, let's solve the problem as if the pizza was a line instead of a cycle. (This is subtask 3.) If the goal is to find the longest segment equal in length to or shorter than
, then the length of a segment can be quickly computed by building a prefix sum array on the line. If the sum of the range
can be found by subtracting position
of the prefix sum array from position
, then for every position
in the line, the largest sum segment ending at
can be computed as the minimum of all positions in the range
in the prefix sum array, subtracted from position
. After building the prefix sum array, a set can be used to solve this (the sliding range minimum query problem) in
, or alternatively, it can be solved in
using a double ended queue.
To solve the problem for a cycle, just arbitrarily choose any starting point, take two periods, and treat it as a line.
Comments