結果

問題 No.3503 Brackets Stack Query 2
コンテスト
ユーザー naz
提出日時 2026-04-17 23:01:26
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
RE  
実行時間 -
コード長 2,826 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 688 ms
コンパイル使用メモリ 20,956 KB
実行使用メモリ 141,472 KB
最終ジャッジ日時 2026-04-17 23:01:54
合計ジャッジ時間 19,008 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other AC * 25 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    input_data = sys.stdin.read().splitlines()
    if not input_data:
        return
    
    q = int(input_data[0])
    
    parent = [0] * (q + 1)
    char_at = [""] * (q + 1)
    depth = [0] * (q + 1)
    
    current_top = 0
    node_count = 0
    
    current_history = [0] * (q + 1)
    
    results = []

    for i in range(1, q + 1):
        line = input_data[i]
        if line[0] == '1':
            c = line[2]
            
            is_match = False
            if c == ')' and depth[current_top] >= 2:
                mid_node = current_top
                top_node = parent[mid_node]
                if char_at[mid_node] == '|' and char_at[top_node] == '(':
                    current_top = parent[top_node]
                    is_match = True
            
            if not is_match:
                node_count += 1
                char_at[node_count] = c
                parent[node_count] = current_top
                depth[node_count] = depth[current_top] + 1
                current_top = node_count
            
            current_history[i] = current_top
        else:
            current_top = current_history[i-1]
            # S'den silme işlemi yapıldığı için bir önceki S durumuna dönülür.
            # Ancak silinen karakterin stack'te neyi temsil ettiğini bilmek için
            # S'in uzunluğunu takip eden bir yapı gerekir. 
            # Bu yüzden Query 2'de bir önceki 'S' adımındaki stack tepesine döneriz.
            # Ama soruda 'S' dizisi değiştiği için i-2. adımdaki stack durumuna dönülür:
            # S'in son halini takip eden bir liste:
            pass

    # Query 2 için daha stabil bir S takibi eklenmiş hali:
    s_stack_tops = [0]
    for i in range(1, q + 1):
        line = input_data[i]
        if line[0] == '1':
            c = line[2]
            prev_top = s_stack_tops[-1]
            new_top = prev_top
            
            matched = False
            if c == ')' and depth[prev_top] >= 2:
                mid = prev_top
                top = parent[mid]
                if char_at[mid] == '|' and char_at[top] == '(':
                    new_top = parent[top]
                    matched = True
            
            if not matched:
                node_count += 1
                char_at[node_count] = c
                parent[node_count] = prev_top
                depth[node_count] = depth[prev_top] + 1
                new_top = node_count
            
            s_stack_tops.append(new_top)
        else:
            if len(s_stack_tops) > 1:
                s_stack_tops.pop()
        
        if s_stack_tops[-1] == 0:
            results.append("Yes")
        else:
            results.append("No")

    sys.stdout.write("\n".join(results) + "\n")

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