#735231 (Scala(Beta)) No.1778 括弧列クエリ / Bracketed Sequence Query

提出ソース

結果

問題	No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー	yudedako
提出日時	2022-01-28 22:28:44
言語	Scala(Beta) (3.4.0)
結果	TLE
実行時間	-
コード長	6,476 bytes
コンパイル時間	12,237 ms
コンパイル使用メモリ	283,292 KB
実行使用メモリ	155,744 KB
最終ジャッジ日時	2024-06-09 15:43:47
合計ジャッジ時間	73,081 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	AC	1,949 ms 79,324 KB
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	AC	1,668 ms 80,032 KB
testcase_07	AC	1,083 ms 71,376 KB
testcase_08	TLE	-
testcase_09	AC	1,489 ms 84,568 KB
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	821 ms 63,588 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	AC	802 ms 63,580 KB
testcase_22	AC	821 ms 63,508 KB
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード