Editorial for LCC '24 Contest 1 S4 - Splitting Candy


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.

Author: AngelsandDevsLOL

Notice that this problem can be solved using prefix sum arrays.

The brands denotated with a 0 will cause a change of -1, and the brands denotated with a 1 will cause a change of 1. If the prefix sum array, a, has the same value at indexes i and j, meaning that ai=aj, then the number of +1s that occur in [i, j - 1] must be equal to the number of 1s.

The index of the last element with the value ai, should be stored to answer the queries. Each query can be answered by the difference between the index given and the index of the last element with the same ai value. Note that if an index array is used to store these values, the values in the prefix sum array cannot be negative. Starting the PSA with an initial value of 105 suffices.


Comments

There are no comments at the moment.