結果

問題 No.875 Range Mindex Query
ユーザー ikdikd
提出日時 2019-09-06 21:40:27
言語 Nim
(2.0.0)
結果
AC  
実行時間 324 ms / 2,000 ms
コード長 1,568 bytes
コンパイル時間 3,226 ms
コンパイル使用メモリ 68,668 KB
実行使用メモリ 17,120 KB
最終ジャッジ日時 2023-09-15 12:51:54
合計ジャッジ時間 6,302 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 2 ms
4,384 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 229 ms
13,912 KB
testcase_12 AC 184 ms
8,268 KB
testcase_13 AC 163 ms
16,044 KB
testcase_14 AC 158 ms
15,252 KB
testcase_15 AC 219 ms
16,276 KB
testcase_16 AC 298 ms
16,232 KB
testcase_17 AC 324 ms
16,856 KB
testcase_18 AC 311 ms
17,120 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 39) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 28) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(1, 39) Warning: imported and not used: 'future' [UnusedImport]

ソースコード

diff #

import strutils, sequtils, algorithm, future, math

const inf = int.high div 3

proc chmin(a: var int, b: int) =
  if a > b: a = b

type SegmentTree = object
  n: int
  dat: seq[int]

proc initSegmentTree(sz: int): SegmentTree =
  result.n = nextPowerOftwo(sz)
  result.dat = newSeqWith(result.n * 2 - 1, inf)

proc update(this: var SegmentTree, i: int, x: int) =
  var k = i + this.n - 1
  this.dat[k] = x
  while k > 0:
    k = (k - 1) div 2
    this.dat[k] = min(this.dat[k * 2 + 1], this.dat[k * 2 + 2])

proc rmin(this: SegmentTree, ql, qr, i, il, ir: int): int =
  if qr <= il or ir <= ql:
    return inf
  elif ql <= il and ir <= qr:
    return this.dat[i]
  else:
    let m = (il + ir) div 2
    result = min(
      this.rmin(ql, qr, i * 2 + 1, il, m), this.rmin(ql, qr, i * 2 + 2, m, ir))

proc rmin(this: SegmentTree, ql, qr: int): int =
  return rmin(this, ql, qr, 0, 0, this.n)

proc get(this: SegmentTree, i: int): int =
  return this.dat[i + this.n - 1]

proc main() =
  var n, q: int
  (n, q) = stdin.readLine.strip.split.map(parseInt)
  let a = stdin.readLine.strip.split.map(parseInt).mapIt(it - 1)
  var
    pos = newSeq[int](n)
    seg = initSegmentTree(n)
  for i in 0..<n:
    pos[a[i]] = i
    seg.update(i, a[i])
  for qq in 0..<q:
    var t, i, j: int
    (t, i, j) = stdin.readLine.strip.split.map(parseInt)
    i -= 1
    j -= 1
    if t == 1:
      let
        ei = seg.get(i)
        ej = seg.get(j)
      seg.update(i, ej)
      seg.update(j, ei)
      pos[ei] = j
      pos[ej] = i
    else:
      echo pos[seg.rmin(i, j + 1)] + 1
main()
0