結果

問題 No.875 Range Mindex Query
ユーザー yakamotoyakamoto
提出日時 2019-09-06 21:43:02
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,018 ms / 2,000 ms
コード長 2,296 bytes
コンパイル時間 15,099 ms
コンパイル使用メモリ 431,564 KB
実行使用メモリ 64,640 KB
最終ジャッジ日時 2023-09-06 23:20:01
合計ジャッジ時間 27,913 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 298 ms
53,176 KB
testcase_01 AC 346 ms
53,536 KB
testcase_02 AC 356 ms
55,792 KB
testcase_03 AC 318 ms
53,204 KB
testcase_04 AC 336 ms
53,568 KB
testcase_05 AC 321 ms
53,248 KB
testcase_06 AC 347 ms
55,300 KB
testcase_07 AC 348 ms
53,604 KB
testcase_08 AC 341 ms
53,656 KB
testcase_09 AC 337 ms
53,480 KB
testcase_10 AC 357 ms
55,632 KB
testcase_11 AC 953 ms
62,180 KB
testcase_12 AC 912 ms
62,824 KB
testcase_13 AC 850 ms
62,132 KB
testcase_14 AC 833 ms
62,436 KB
testcase_15 AC 927 ms
62,228 KB
testcase_16 AC 956 ms
64,640 KB
testcase_17 AC 989 ms
64,248 KB
testcase_18 AC 1,018 ms
64,184 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