結果

問題 No.875 Range Mindex Query
ユーザー yakamotoyakamoto
提出日時 2019-09-06 21:43:02
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,007 ms / 2,000 ms
コード長 2,296 bytes
コンパイル時間 13,268 ms
コンパイル使用メモリ 446,972 KB
実行使用メモリ 91,004 KB
最終ジャッジ日時 2024-06-24 17:20:01
合計ジャッジ時間 25,995 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 304 ms
52,056 KB
testcase_01 AC 357 ms
53,284 KB
testcase_02 AC 370 ms
53,488 KB
testcase_03 AC 318 ms
52,196 KB
testcase_04 AC 334 ms
52,904 KB
testcase_05 AC 325 ms
52,740 KB
testcase_06 AC 354 ms
53,236 KB
testcase_07 AC 359 ms
53,052 KB
testcase_08 AC 349 ms
52,972 KB
testcase_09 AC 337 ms
52,844 KB
testcase_10 AC 364 ms
53,912 KB
testcase_11 AC 935 ms
89,956 KB
testcase_12 AC 907 ms
90,028 KB
testcase_13 AC 859 ms
90,004 KB
testcase_14 AC 843 ms
90,052 KB
testcase_15 AC 924 ms
90,060 KB
testcase_16 AC 970 ms
89,784 KB
testcase_17 AC 985 ms
90,964 KB
testcase_18 AC 1,007 ms
91,004 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import kotlin.math.max
import kotlin.math.min

// なんか本番でエラーでる
private val isDebug = runCatching {
  System.getenv("MY_DEBUG") != null
}.fold({it}, {false})

private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }.toIntArray()
private fun readLongs() = readStrings().map { it.toLong() }.toLongArray()
private fun debug(msg: () -> String) {
  if (isDebug) System.err.println(msg())
}
private fun debug(a: LongArray) {
  if (isDebug) debug{a.joinToString(" ")}
}
private fun debug(a: IntArray) {
  if (isDebug) debug{a.joinToString(" ")}
}
private fun debugDim(A: Array<IntArray>) {
  if (isDebug) {
    for (a in A) {
      debug(a)
    }
  }
}

val MOD = 1000000007

class SegmentTree(n: Int, val zero: Int, val f: (Int, Int) -> Int) {
  private val N =
    if (Integer.highestOneBit(n) == n) n
    else Integer.highestOneBit(n) shl 1

  private val dat = IntArray(2 * N){zero}

  fun update(i: Int, a: Int) {
    var ix = i + N
    dat[ix] = a
    while(ix > 1) {
      dat[ix shr 1] = f(dat[ix], dat[ix xor 1])
      ix = ix shr 1
    }
  }

  /**
    * [a, b)
    */
  fun query(a: Int, b: Int): Int {
    var res: Int = zero
    var left = a + N
    var right = b - 1 + N

    while(left <= right) {
      if ((left and 1) == 1) res = f(res, dat[left])
      if ((right and 1) == 0) res = f(res, dat[right])
      left = (left + 1) shr 1 // 右の子供なら右の親に移動
      right = (right - 1) shr 1 // 左の子供なら左の親に移動
    }

    return res
  }
}

fun main() {
  val (N, Q) = readInts()
  val A = IntArray(N + 1)
  for ((i, a) in readInts().withIndex()) {
    A[i] = a
  }
  A[N] = N + 10
  debug(A)

  val seg = SegmentTree(N, N) { a, b ->
    if (A[a] < A[b]) a else b
  }
  repeat(N) {
    seg.update(it, it)
  }

  val ans = mutableListOf<Int>()
  repeat(Q) {
    var (type, l, r) = readInts()
    l--; r--
    when(type) {
      1 -> {
        val oldL = A[l]
        val oldR = A[r]
        A[l] = oldR
        A[r] = oldL
        seg.update(l, l)
        seg.update(r, r)
        debug(A)
      }
      2 -> {
        ans += seg.query(l, r + 1) + 1
      }
    }
  }

  println(ans.joinToString("\n"))
}
0