結果

問題 No.875 Range Mindex Query
ユーザー nadeshinonadeshino
提出日時 2020-01-25 15:29:17
言語 Nim
(2.0.2)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 2,891 bytes
コンパイル時間 3,434 ms
コンパイル使用メモリ 71,692 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2024-09-14 04:05:41
合計ジャッジ時間 7,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 4 ms
6,940 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 4 ms
6,940 KB
testcase_11 AC 352 ms
8,704 KB
testcase_12 AC 285 ms
6,940 KB
testcase_13 AC 234 ms
8,832 KB
testcase_14 AC 228 ms
8,576 KB
testcase_15 AC 337 ms
8,704 KB
testcase_16 AC 401 ms
8,704 KB
testcase_17 AC 431 ms
8,704 KB
testcase_18 AC 449 ms
8,576 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