結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー Schnee
提出日時 2021-12-08 00:08:08
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,459 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-07-08 03:54:16
合計ジャッジ時間 14,947 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 4 TLE * 2 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

input = sys.stdin.readline

def int_input():
    return map(int,input().split())

n, q = int_input()
s = input()

def find_pair(x):
    count_dis = 1
    sign = [-1, 1][s[x - 1] == "("]
    for i in range(1, n):
        i *= sign
        if s[x - 1 + i] == "(":
            count_dis += sign
        else:
            count_dis -= sign
        if count_dis == 0:
            return x + i

def find_set_b(x):
    count_dis = 0
    for i in range(1, x):
        if s[x-1-i]==")":
            count_dis -= 1
        else:
            count_dis += 1
            if count_dis == 1:
                return x - i

def find_set_t(x):
    count_dis = 0
    for i in range(1, n - x + 1):
        if s[x-1+i]=="(":
            count_dis -= 1
        else:
            count_dis += 1
            if count_dis == 1:
                return x + i

def compare_2set(x, y):
    x_min, x_max = min(x), max(x)
    y_min, y_max = min(y), max(y)
    if x_min <= y_min and x_max >= y_max:
        return x_min, x_max
    elif y_min <= x_min and y_max >= x_max:
        return y_min, y_max
    else:
        None

for _ in range(q):
    a, b = int_input()
    x, y = [a, find_pair(a)], [b, find_pair(b)]
    if ret:= compare_2set(x, y):
        print(*ret)
    
    else:
        top, bottom = max(*x, *y), min(*x, *y)
        a_b = find_set_b(bottom)
        a_t = find_set_t(top)
        if a_b and a_t:
            print(a_b, a_t)
        else:
            print(-1)
0