結果

問題 No.3009 Union-Find でつながろう！
ユーザー qwewe
提出日時 2025-05-14 13:10:44
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,070 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,896 KB
実行使用メモリ 67,516 KB
最終ジャッジ日時 2025-05-14 13:12:09
合計ジャッジ時間 3,503 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Use sys.stdin.readline for potentially faster I/O in competitive programming environments.
# Assign it to a variable `input` for convenience, mimicking the standard input() function.
input = sys.stdin.readline

def solve():
    # Read the integer N, which represents the number of elements in the sequence.
    N = int(input())
    
    # Handle the edge case where N is 0. 
    # An empty sequence has no subarrays, so the maximum length is 0.
    if N == 0:
        print(0)
        return

    # Read the sequence of N integers. 
    # The integers are provided on a single line, separated by spaces.
    # map(int, input().split()) reads the line, splits it into strings by spaces, 
    # and converts each string part to an integer. list() converts the map object to a list.
    A = list(map(int, input().split()))

    # Initialize variables for the sliding window algorithm.
    max_length = 0  # This variable will store the maximum length found so far. Initialize to 0.
    left = 0        # This is the left pointer (start index) of the sliding window. Initialize to 0.
                    # The window is represented by the indices [left, right].
    last_seen = {}  # This dictionary will store the last seen index for each number encountered.
                    # The format is {number: index}. This helps efficiently check for duplicates.

    # Iterate through the array using a 'right' pointer. 
    # The `right` pointer represents the right boundary (end index) of the current window being considered.
    # It iterates from index 0 to N-1.
    for right in range(N):
        # Get the number at the current `right` pointer position.
        current_num = A[right]

        # Check if the current number `current_num` has been seen before.
        # We check if it exists as a key in the `last_seen` dictionary.
        if current_num in last_seen:
            # If `current_num` has been seen before, let `last_idx` be its last seen index.
            # We need to check if this `last_idx` falls within the current active window defined by `left`.
            # The condition `last_seen[current_num] >= left` checks this.
            # If true, it means `current_num` already exists in the subarray A[left...right-1].
            # Including A[right] (which is `current_num`) would violate the distinctness property.
            # To fix this, we must slide the `left` pointer forward. The new `left` must be at least
            # one position after the previous occurrence of `current_num`. That is, `last_seen[current_num] + 1`.
            # We use `max(left, ...)` to ensure that the `left` pointer only moves forward (non-decreasing).
            # This is important because `left` might have already been moved forward due to another duplicate element.
            left = max(left, last_seen[current_num] + 1)

        # Update the `last_seen` dictionary. Record that `current_num` was last encountered at the current index `right`.
        # If `current_num` was already in the dictionary, its value (last seen index) is updated.
        last_seen[current_num] = right

        # Calculate the length of the current window `A[left ... right]`.
        # This window is guaranteed to contain distinct elements after potentially adjusting `left`.
        # The length of the subarray from index `left` to `right` (inclusive) is `right - left + 1`.
        current_length = right - left + 1
        
        # Update `max_length` if the length of the current window (`current_length`) is greater than
        # the maximum length found so far (`max_length`).
        max_length = max(max_length, current_length)

    # After iterating through all possible `right` boundaries (i.e., considering all possible ending positions for subarrays),
    # `max_length` will hold the maximum length of any subarray with distinct elements found in the sequence A.
    # Print the final result. `print()` automatically adds a newline character at the end.
    print(max_length)

# Call the `solve` function to execute the program logic.
solve()
0