結果

問題 No.2170 Left Addition Machine
ユーザー qwewe
提出日時 2025-05-14 13:10:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,203 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 53,320 KB
最終ジャッジ日時 2025-05-14 13:11:57
合計ジャッジ時間 8,261 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to solve the problem
def solve():
    # Read N and Q
    N, Q = map(int, sys.stdin.readline().split())
    
    # Read the initial array A
    A = list(map(int, sys.stdin.readline().split()))
    
    # Define the modulus
    MOD = 998244353

    # List to store results for each query
    results = []

    # Process each query
    for _ in range(Q):
        # Read query bounds L and R (1-based)
        L, R = map(int, sys.stdin.readline().split())
        
        # Create a list representing the current sequence B for the subarray A[L-1...R-1]
        # Each element in B is a list: [original_index_in_A, current_value]
        # We use lists for elements because values will be modified.
        # The original index is needed for tie-breaking when finding the leftmost maximum.
        B = []
        for i in range(L - 1, R):
             # The original index is i, the value is A[i]
             B.append([i, A[i]]) 

        # Get the current length of the sequence B
        current_len = R - L + 1

        # If the initial sequence length is 1, the result is just the single element's value.
        # The loop below only runs if current_len > 1.
        if current_len == 1:
            results.append(B[0][1])
            continue

        # Simulate the Left Addition Machine process
        # Repeat until the sequence length becomes 1
        while current_len > 1:
            
            # Variables to find the leftmost maximum element
            max_val = -1 # Maximum value found so far
            target_idx_in_B_list = -1 # Index within the list B where the leftmost max is found
            leftmost_orig_idx = N + 1 # Track the original index from A for tie-breaking (smallest index wins)

            # Iterate through the current elements in B to find the leftmost maximum
            # This loop takes O(current_len) time.
            for k in range(len(B)):
                orig_idx, val = B[k] # Unpack original index and current value
                
                # Check if current element's value is greater than max_val found so far
                if val > max_val:
                    max_val = val
                    target_idx_in_B_list = k # Update target index
                    leftmost_orig_idx = orig_idx # Update leftmost original index
                # Check if current element's value is equal to max_val
                elif val == max_val:
                    # If values are equal, choose the one with the smaller original index (leftmost)
                    if orig_idx < leftmost_orig_idx:
                         # Found an element with the same max value but appearing earlier in the original array A
                         target_idx_in_B_list = k # Update target index
                         leftmost_orig_idx = orig_idx # Update leftmost original index

            # Get the value of the selected element (leftmost maximum)
            val_to_add = B[target_idx_in_B_list][1]

            # Perform updates: add val_to_add to elements to the left of the selected element
            # The elements to the left are those with index k < target_idx_in_B_list in the current list B
            # This update step takes O(target_idx_in_B_list), which is O(current_len) in the worst case.
            for k in range(target_idx_in_B_list):
                # Update value modulo MOD
                B[k][1] = (B[k][1] + val_to_add) % MOD
            
            # Remove the selected element from B using list.pop
            # pop(idx) takes O(len(B) - idx) time, which is O(current_len) in the worst case.
            B.pop(target_idx_in_B_list)
            
            # Decrease the length of the sequence
            current_len -= 1 
            
        # After the loop finishes, B contains exactly one element. Append its value to results.
        # The check `if B:` from previous thought is not strictly necessary because the loop
        # terminates when current_len is 1, meaning B will always have one element.
        results.append(B[0][1])

    # Print all computed results, each on a new line
    for res in results:
        print(res)

# Call the solve function to run the program
solve()
0