結果
| 問題 |
No.1778 括弧列クエリ / Bracketed Sequence Query
|
| コンテスト | |
| ユーザー |
 yudedako
|
| 提出日時 | 2022-01-28 22:28:44 |
| 言語 | Scala(Beta) (3.6.2) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,476 bytes |
| コンパイル時間 | 17,770 ms |
| コンパイル使用メモリ | 270,540 KB |
| 実行使用メモリ | 253,136 KB |
| 最終ジャッジ日時 | 2024-12-30 08:23:33 |
| 合計ジャッジ時間 | 95,622 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 4 TLE * 23 |
ソースコード
import scala.annotation.tailrec
import scala.collection.immutable
import scala.collection.immutable.TreeSet
import scala.io.StdIn.readLine
import scala.math.*
import scala.annotation.tailrec
object Patricia:
private sealed trait Node:
val prefix: Int
private object Node:
private def leftMostOne(value: Int): Int =
var result = 0
for i <- Array(4, 3, 2, 1, 0) do
if value >>> (result + (1 << i)) > 0 then
result += 1 << i
1 << result
private def apply(left: Node, right: Node): Node =
val mask = -leftMostOne(left.prefix ^ right.prefix)
val prefix = (left.prefix | right.prefix) & mask
assert(mask == -(prefix & -prefix))
assert(left.prefix < right.prefix)
assert(((left.prefix ^ right.prefix) & (mask << 1)) == 0 && ((left.prefix ^ right.prefix) & mask) != 0)
Branch(prefix, left, right)
def insert(node: Node, newValue: Int): Node =
node match
case Branch(prefix, left, right) =>
val mask = -(prefix & -prefix) << 1
assert(((left.prefix ^ right.prefix) & mask) == 0 && ((left.prefix ^ right.prefix) & -(prefix & -prefix)) != 0, s"prefix: ${prefix.toBinaryString}, left: ${left.prefix.toBinaryString}, right: ${right.prefix.toBinaryString}")
if (prefix & mask) != (newValue & mask) then
if prefix < newValue then Node(node, Leaf(newValue))
else Node(Leaf(newValue), node)
else
if newValue < (prefix & right.prefix) then
val newLeft = insert(left, newValue)
if newLeft eq left then node
else Branch(prefix, newLeft, right)
else
val newRight = insert(right, newValue)
if newRight eq right then node
else Branch(prefix, left, newRight)
case Leaf(prefix) =>
if prefix == newValue then node
else if prefix < newValue then Node(node, Leaf(newValue))
else Node(Leaf(newValue), node)
def erase(node: Node, value: Int): Option[Node] =
node match
case Branch(prefix, left, right) =>
val mask = -(prefix & -prefix) << 1
if (prefix & mask) != (value & mask) then Some(node)
else
if value < (right.prefix & prefix) then
erase(left, value) match
case Some(newLeft) =>
if newLeft eq left then Some(node)
else Some(Node(newLeft, right))
case None => Some(right)
else
erase(right, value) match
case Some(newRight) =>
if newRight eq right then Some(node)
else Some(Node(left, newRight))
case None => Some(left)
case Leaf(oldValue) =>
if oldValue == value then None
else Some(node)
@tailrec def minValue(node: Node): Int =
node match
case Branch(_, left, _) => minValue(left)
case Leaf(prefix) => prefix
def lowerBound(node: Node, value: Int): Option[Int] =
node match
case Branch(prefix, left , right) =>
val mask = -(prefix & -prefix) << 1
if (prefix & mask) < (value & mask) then None
if (value & mask) < (prefix & mask) then Some(minValue(left))
else if value < (right.prefix & prefix) then Some(lowerBound(left, value).getOrElse(minValue(right)))
else lowerBound(right, value)
case Leaf(prefix) =>
if prefix < value then None
else Some(prefix)
def upperBound(node: Node, value: Int): Option[Int] =
node match
case Branch(prefix, left , right) =>
val mask = -(prefix & -prefix) << 1
if (prefix & mask) < (value & mask) then None
else if (value & mask) < (prefix & mask) then Some(minValue(left))
else if value < (right.prefix & prefix) then Some(upperBound(left, value).getOrElse(minValue(right)))
else upperBound(right, value)
case Leaf(prefix) =>
if prefix <= value then None
else Some(prefix)
def copyToArray(node: Node, dest: Array[Int], position: Int): Int =
node match
case Branch(prefix, left, right) =>
copyToArray(right, dest, copyToArray(left, dest, position))
case Leaf(prefix) =>
dest(position) = prefix
position + 1
private case class Branch(override val prefix: Int, val left: Node, val right: Node) extends Node
private case class Leaf(override val prefix: Int) extends Node
class Patricia private(private val root: Option[Patricia.Node], val size: Int):
import Patricia.Node.*
import Patricia.*
def this() =
this(None, 0)
def inserted(value: Int): Patricia =
root match
case Some(r) =>
val newRoot = insert(r, value)
if newRoot eq r then this
else Patricia(Some(newRoot), size + 1)
case None => Patricia(Some(Patricia.Leaf(value)), 1)
def erased(value: Int): Patricia =
root match
case Some(r) =>
erase(r, value) match
case Some(newRoot) =>
if newRoot eq r then this
else Patricia(Some(newRoot), size - 1)
case None => Patricia(None, 0)
case None => this
def lowerBound(value: Int): Option[Int] =
root.flatMap(Node.lowerBound(_, value))
def upperBound(value: Int): Option[Int] =
root.flatMap(Node.upperBound(_, value))
def toArray: Array[Int] =
root match
case Some(r) =>
val result = Array.fill(size){0}
copyToArray(r, result, 0)
result
case None => Array()
def +(value: Int): Patricia = inserted(value)
def minAfter(value: Int): Option[Int] = lowerBound(value)
@main def main =
val Array(n, q) = readLine().split(' ').map(_.toInt)
val s = readLine()
val queries = Array.fill(q){
val Array(x, y) = readLine().split(' ').map(_.toInt - 1)
min(x, y) -> max(x, y)
}
var stack = Nil: List[Int]
val pair = Array.fill(n){-1}
for (c, i) <- s.zipWithIndex do
c match
case '(' => stack ::= i
case ')' =>
val h::t = stack
pair(i) = h
pair(h) = i
stack = t
val set = Array.fill(n){Patricia()}
for i <- 0 until n do
if i > 0 then
set(i) = set(i - 1)
if s(i) == '(' then
set(i) = set(i) + pair(i)
for (x, y) <- queries do
val result = set(x).minAfter(y).map(right => s"${pair(right) + 1} ${right + 1}").getOrElse("-1")
println(result)