結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー yudedakoyudedako
提出日時 2022-01-28 23:21:52
言語 Kotlin
(1.9.23)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,054 bytes
コンパイル時間 16,813 ms
コンパイル使用メモリ 427,612 KB
実行使用メモリ 100,356 KB
最終ジャッジ日時 2023-08-28 21:59:06
合計ジャッジ時間 60,806 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,149 ms
71,304 KB
testcase_01 AC 1,192 ms
71,636 KB
testcase_02 AC 1,190 ms
71,716 KB
testcase_03 AC 1,146 ms
69,940 KB
testcase_04 AC 1,241 ms
73,640 KB
testcase_05 AC 1,444 ms
74,464 KB
testcase_06 AC 1,188 ms
65,620 KB
testcase_07 AC 500 ms
58,236 KB
testcase_08 AC 1,826 ms
95,816 KB
testcase_09 AC 751 ms
63,032 KB
testcase_10 AC 1,234 ms
74,336 KB
testcase_11 AC 1,257 ms
71,976 KB
testcase_12 AC 1,446 ms
77,292 KB
testcase_13 AC 1,722 ms
94,560 KB
testcase_14 AC 1,277 ms
70,068 KB
testcase_15 AC 339 ms
57,000 KB
testcase_16 AC 1,962 ms
99,480 KB
testcase_17 AC 1,804 ms
95,716 KB
testcase_18 AC 1,908 ms
99,164 KB
testcase_19 AC 1,849 ms
95,472 KB
testcase_20 AC 1,835 ms
95,668 KB
testcase_21 AC 329 ms
57,084 KB
testcase_22 AC 325 ms
56,968 KB
testcase_23 AC 1,778 ms
82,444 KB
testcase_24 AC 1,775 ms
84,492 KB
testcase_25 AC 1,772 ms
97,288 KB
testcase_26 TLE -
testcase_27 AC 1,127 ms
80,372 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