結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー yudedakoyudedako
提出日時 2022-01-28 23:21:52
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,634 ms / 2,000 ms
コード長 1,054 bytes
コンパイル時間 15,579 ms
コンパイル使用メモリ 442,308 KB
実行使用メモリ 114,096 KB
最終ジャッジ日時 2024-06-09 16:54:47
合計ジャッジ時間 49,706 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,038 ms
96,632 KB
testcase_01 AC 1,044 ms
96,740 KB
testcase_02 AC 1,025 ms
96,976 KB
testcase_03 AC 965 ms
96,952 KB
testcase_04 AC 1,123 ms
96,840 KB
testcase_05 AC 1,179 ms
93,280 KB
testcase_06 AC 945 ms
89,840 KB
testcase_07 AC 438 ms
59,148 KB
testcase_08 AC 1,607 ms
113,500 KB
testcase_09 AC 687 ms
77,252 KB
testcase_10 AC 1,068 ms
93,920 KB
testcase_11 AC 1,020 ms
90,840 KB
testcase_12 AC 1,161 ms
102,488 KB
testcase_13 AC 1,409 ms
113,596 KB
testcase_14 AC 1,002 ms
90,720 KB
testcase_15 AC 297 ms
55,528 KB
testcase_16 AC 1,623 ms
112,148 KB
testcase_17 AC 1,504 ms
114,096 KB
testcase_18 AC 1,525 ms
111,356 KB
testcase_19 AC 1,445 ms
111,876 KB
testcase_20 AC 1,550 ms
112,244 KB
testcase_21 AC 295 ms
55,320 KB
testcase_22 AC 343 ms
55,160 KB
testcase_23 AC 1,477 ms
111,616 KB
testcase_24 AC 1,469 ms
107,496 KB
testcase_25 AC 1,424 ms
111,296 KB
testcase_26 AC 1,634 ms
110,120 KB
testcase_27 AC 1,026 ms
101,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*

fun main() {
    val (n, q) = readLine()!!.split(' ').map(String::toInt)
    val s = readLine()!!
    val queries = List(q) {
        val (x, y) = readLine()!!.trim().split(' ').map(String::toInt)
        minOf(x, y) - 1 to maxOf(x, y) - 1
    }
    val stack = mutableListOf<Int>()
    val pair = IntArray(n)
    for (i in s.indices) {
        when(s[i]) {
            '(' -> stack.add(i)
            ')' -> {
                val l = stack.removeLast()
                pair[l] = i
                pair[i] = l
            }
        }
    }
    val set = TreeSet<Int>()
    var last = 0
    val result = IntArray(q){-1}
    for ((index, p) in queries.withIndex().sortedBy { it.value.first }) {
        val (min, max) = p
        while (last < n && last <= min) {
            if (s[last] == '(') {
                set.add(pair[last])
            }
            last += 1
        }
        result[index] = set.higher(max - 1) ?: continue
    }
    println(result.joinToString("\n"){i -> if (i >= 0) "${pair[i] + 1} ${i + 1}" else "-1"})
}
0