Overview

When performing songs in order, only songs with a higher difficulty than the immediately preceding song have their performance time halved (rounded down). The problem asks you to calculate the total time according to this rule.

Analysis

The key point is that “each song’s performance time is determined solely by the comparison \(D_{i-1} < D_i\) with the immediately preceding song.”
In other words, the time for the \(i\)-th song is:

• When \(i=1\): always \(D_1\)
• When \(i\ge 2\):
  • If \(D_{i-1} < D_i\), then \(\left\lfloor \dfrac{D_i}{2} \right\rfloor\)
  • Otherwise, \(D_i\)

You don’t need to be aware of “entire consecutively increasing segments” — it suffices to just compare each \(i\) with its predecessor (whether the increase continues is automatically reflected by checking \(D_{i-1} < D_i\) each time).

Concrete Example

When \(D=[3,5,4,6]\): - Song 1: \(3\) - Song 2: \(3<5\), so \(\lfloor 5/2 \rfloor =2\) - Song 3: \(5<4\) is false, so \(4\) - Song 4: \(4<6\), so \(\lfloor 6/2 \rfloor =3\)

The total is \(3+2+4+3=12\) minutes.

You could also “find increasing segments and process them together,” but since it all boils down to repeated adjacent comparisons, a single pass is sufficient. Since \(N\le 2\times 10^5\), an \(O(N)\) solution easily fits within the time limit.

Algorithm

1. Initialize the total time total with \(D_1\) (the first song always takes its full duration).
2. Iterate from \(i=2\) to \(N\):
   • If \(D_{i-1} < D_i\), then total += D_i // 2
   • Otherwise, total += D_i
3. Output total.

Complexity

• Time complexity: \(O(N)\) (a single loop comparing adjacent elements)
• Space complexity: \(O(N)\) (storing the input array; could be done with sequential reading, but this implementation stores it in an array)

Implementation Notes

• “Half” means rounded down, so in Python use integer division D_i // 2.

• The first song always takes \(D_1\) minutes as a special case, so it’s simplest to add it as the initial value and then process from \(i=1\) (the 2nd song in 0-indexed) onward.

• Since the input can be up to \(2\times 10^5\) elements, using sys.stdin.buffer.read() allows for faster reading.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    d = data[1:1+n]

    total = d[0]
    for i in range(1, n):
        if d[i-1] < d[i]:
            total += d[i] // 2
        else:
            total += d[i]
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.