結果

問題 No.875 Range Mindex Query
ユーザー nadeshinonadeshino
提出日時 2020-01-25 15:29:17
言語 Nim
(2.0.2)
結果
AC  
実行時間 483 ms / 2,000 ms
コード長 2,891 bytes
コンパイル時間 3,193 ms
コンパイル使用メモリ 69,536 KB
実行使用メモリ 11,932 KB
最終ジャッジ日時 2023-10-12 04:34:51
合計ジャッジ時間 7,433 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 4 ms
4,348 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 3 ms
4,352 KB
testcase_05 AC 2 ms
4,352 KB
testcase_06 AC 3 ms
4,348 KB
testcase_07 AC 4 ms
4,352 KB
testcase_08 AC 3 ms
4,348 KB
testcase_09 AC 3 ms
4,352 KB
testcase_10 AC 4 ms
4,352 KB
testcase_11 AC 399 ms
10,436 KB
testcase_12 AC 327 ms
8,460 KB
testcase_13 AC 270 ms
11,092 KB
testcase_14 AC 264 ms
10,860 KB
testcase_15 AC 385 ms
11,364 KB
testcase_16 AC 435 ms
11,280 KB
testcase_17 AC 464 ms
11,612 KB
testcase_18 AC 483 ms
11,932 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 36) Warning: imported and not used: 'math' [UnusedImport]
/home/judge/data/code/Main.nim(1, 19) Warning: imported and not used: 'complex' [UnusedImport]

ソースコード

diff # 

import algorithm, complex, macros, math, sequtils, sets, strutils, tables

macro unpack*(rhs: seq, cnt: static[int]): auto =
  let v = genSym(); result = quote do:(let `v` = `rhs`;())
  if NimMajor == 0 and NimMinor <= 17:
    for i in 0 ..< cnt: result[0][1].add(quote do:`v`[`i`])
  else:
    for i in 0 ..< cnt: result[1].add(quote do:`v`[`i`])

template input*(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseint)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc `|=`*(n: var int, m: int) = n = n or m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
proc `%=`*(n: var int, m: int) = n = n mod m
proc `/=`*(n: var int, m: int) = n = n div m
proc `<<=`*(n: var int, m: int) = n = n shl m
proc `>>=`*(n: var int, m: int) = n = n shr m
proc `<?=`*(n: var SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))

# -------------------------------------------------- #

let (N, Q) = input(int, 2)
var A = @[0] & input(seq[int])

const bsize = 317
let K = (N + bsize - 1) div bsize
var bucket = newSeq[int](K + 1)
bucket.fill(N + 1)
for d in 1 .. K:
  for j in 1 .. bsize:
    let i = (d - 1) * bsize + j
    if i <= N:
      bucket[d] <?= A[i]
    else:
      break

proc update(d: int) =
  bucket[d] = N + 1
  let a = (d - 1) * bsize + 1
  let b = min(d * bsize, N)
  for i in a .. b:
    bucket[d] <?= A[i]

proc query1(L: int, R: int) =
  swap(A[L], A[R])
  let d1 = (L - 1) div bsize + 1
  let d2 = (R - 1) div bsize + 1
  update(d1); update(d2)

proc query2(L: int, R: int) =
  var res = (minv: N + 1, idx: -1, bucket: -1)
  for d in 1 .. K:
    let a = (d - 1) * bsize + 1
    let b = d * bsize
    if L <= a and b <= R:
      if bucket[d] < res.minv:
        res = (bucket[d], -1, d)
    else:
      for i in max(a, L) .. min(b, R):
        if A[i] < res.minv:
          res = (A[i], i, -1)
  if res.idx != -1:
    echo res.idx
    return
  else:
    let d = res.bucket
    let a = (d - 1) * bsize + 1
    let b = d * bsize
    for i in a .. b:
      if res.minv == A[i]:
        echo i
        return

for _ in 1 .. Q:
  let (T, L, R) = input(int, 3)
  if T == 1:
    query1(L, R)
  elif T == 2:
    query2(L, R)
0