Overview

Determine whether the snowfall on each day exceeds the maximum snowfall observed up to that point. Output a string concatenating o if it sets a new record, and x otherwise, in chronological order.

Analysis

The condition for day \(i\) to set a new record is that \(A_i\) is strictly greater than the snowfall on all previous days.

Naively, this can be checked by examining all preceding days for each day. This approach takes \(O(N^2)\) time, which easily runs within the time limit under the given constraints.

However, there is no need to re-examine all past snowfalls every time. By only keeping track of the maximum value so far, we can determine the result simply by comparing against this value.

Let mx be the maximum value up to that point:

• If \(A_i > \mathrm{mx}\), it is a new record, so record o and update mx to \(A_i\).
• If \(A_i \leq \mathrm{mx}\), it is not a new record, so record x and leave mx unchanged.

Note that a value equal to the maximum does not count as a new record.

For example, if the snowfalls are \([2, 5, 5, 1, 7]\), the process is as follows:

Day	Snowfall	Maximum so far	Result
\(1\)	\(2\)	None	o
\(2\)	\(5\)	\(2\)	o
\(3\)	\(5\)	\(5\)	x
\(4\)	\(1\)	\(5\)	x
\(5\)	\(7\)	\(5\)	o

Therefore, the output is ooxxo.

Algorithm

1. Prepare an empty list ans to store the characters of the answer.
2. Initialize the maximum value so far, mx, to \(-1\).
3. Iterate through the snowfalls from beginning to end, letting the current value be v:
   • If v > mx, append o to ans and update mx to v.
   • Otherwise, append x to ans.
4. Concatenate the characters in ans and output the result.

Since the constraints guarantee \(A_i \geq 0\), initializing mx to \(-1\) ensures that day \(1\) will always be evaluated as o.

Moreover, after processing each day, mx will be the maximum value up to that day. Thus, the next day can be correctly compared against the maximum of all prior days, allowing all days to be evaluated correctly.

Complexity

• Time Complexity: \(O(N)\)
  Each day is evaluated once, and concatenating the final string also takes \(O(N)\) time.
• Space Complexity: \(O(N)\)
  Uses space for the input array and the list storing the answer. Tracking the maximum value itself requires only \(O(1)\) additional space.

Implementation Notes

• The condition for a new record is v > mx. If you use v >= mx, values equal to the previous maximum will be incorrectly evaluated as new records.

• If mx is initialized to \(0\), day \(1\) will result in x when \(A_1 = 0\). The implementation uses \(-1\), which is smaller than any possible snowfall.

• Using ''.join(ans) allows you to concatenate the characters stored in the list without spaces.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    ans = []
    mx = -1  # A_i >= 0, so day 1 is always a new record
    for v in a:
        if v > mx:
            ans.append('o')
            mx = v
        else:
            ans.append('x')
    print(''.join(ans))

main()

---

This editorial was generated by gpt-6-astra-medium.