結果

問題 No.2036 Max Middle
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:47:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,699 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 83,020 KB
実行使用メモリ 297,832 KB
最終ジャッジ日時 2025-03-31 17:48:02
合計ジャッジ時間 4,369 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N_and_rest = list(map(int, sys.stdin.read().split()))
    N = N_and_rest[0]
    A = N_and_rest[1:N+1]
    
    initial_peaks = []
    for i in range(N - 2):
        if A[i] < A[i + 1] and A[i + 1] > A[i + 2]:
            initial_peaks.append(i)
    
    in_queue = [False] * (N - 2)
    q = deque()
    for i in initial_peaks:
        q.append(i)
        in_queue[i] = True
    
    count = 0
    
    while q:
        i = q.popleft()
        in_queue[i] = False
        
        # Check if the current triplet is still a peak
        if i + 2 >= N:
            continue
        a = A[i]
        b = A[i + 1]
        c = A[i + 2]
        if a < b and b > c:
            # Process the peak
            min_val = min(a, c)
            new_b = min_val - 1
            A[i + 1] = new_b
            count += 1
            
            # Check left neighbor triplet (i-1)
            left_i = i - 1
            if left_i >= 0 and left_i < (N - 2):
                if not in_queue[left_i]:
                    is_peak = (A[left_i] < A[left_i + 1] and A[left_i + 1] > A[left_i + 2])
                    if is_peak:
                        q.append(left_i)
                        in_queue[left_i] = True
            
            # Check right neighbor triplet (i+1)
            right_i = i + 1
            if right_i < (N - 2):
                if not in_queue[right_i]:
                    is_peak = (A[right_i] < A[right_i + 1] and A[right_i + 1] > A[right_i + 2])
                    if is_peak:
                        q.append(right_i)
                        in_queue[right_i] = True
    
    print(count)

if __name__ == "__main__":
    main()
0