#395100 (Nim) No.875 Range Mindex Query

提出ソース

結果

問題	No.875 Range Mindex Query
ユーザー	zer0-star
提出日時	2019-10-31 23:33:19
言語	Nim (2.0.2)
結果	CE (最新) AC (最初)
実行時間	-
コード長	7,033 bytes
コンパイル時間	862 ms
コンパイル使用メモリ	66,616 KB
最終ジャッジ日時	2024-11-14 21:48:54
合計ジャッジ時間	1,466 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

/home/judge/data/code/Main.nim(244, 34) Error: undeclared identifier: 'N'

ソースコード

raw source code

#=== Template_Base =========================== {{{

import strutils, sequtils, math, algorithm, macros
when (not (NimMajor <= 0)) or NimMinor >= 19:
  import sugar
else:
  import future

# type
#   si = seq[int]
#   ssi = seq[seq[int]]
#   sf = seq[float]
#   ssf = seq[seq[float]]

# proc r(): string = stdin.readLine
# proc ri(): int = r().parseInt
# proc rsi(): seq[int] = r().split.map(parseInt)
# proc rf(): float = r().parseFloat
# proc rsf(): seq[float] = r().split.map(parseFloat)
# proc rn(n: int): seq[string] =
#   result = @[]
#   for i in 1..n:
#     result.add(r())
# proc rin(n: int): seq[int] =
#   result = @[]
#   for i in 1..n:
#     result.add(ri())
# proc rsin(n: int): seq[seq[int]] =
#   result = @[]
#   for i in 1..n:
#     result.add(rsi())
iterator range(x, y: int): int {.inline.} =
  var res = x
  while res < y:
    yield res
    inc(res)
iterator range(x: int): int {.inline.} =
  var res = 0
  while res < x:
    yield res
    inc(res)
proc range(x, y: int): seq[int] {.inline.} =
  toSeq(x..y-1)
proc range(x: int): seq[int] {.inline.} =
  toSeq(0..x-1)
proc discardableId[T](x: T): T {.discardable.} =
  return x
template `:=`(x, y: untyped): untyped =
  when defined(x):
    (x = y; discardableId(x))
  else:
    (var x = y; discardableId(x))
when NimMajor <= 0 and NimMinor <= 17:
  proc count[T](co: openArray[T]; obj: T): int =
    for itm in items(co):
      if itm == obj:
        inc result
proc divmod(x, y: SomeInteger): (int, int) =
  (x div y, x mod y)
proc `min=`[T](x: var T; y: T): bool {.discardable.} =
  if x > y:
    x = y
    return true
  else:
    return false
proc `max=`[T](x: var T; y: T): bool {.discardable.} =
  if x < y:
    x = y
    return true
  else:
    return false

when NimMajor <= 0 and NimMinor <= 17:
  iterator pairs(n: NimNode): (int, NimNode) {.inline.} =
    for i in 0 ..< n.len:
      yield (i, n[i])

when NimMajor <= 0 and NimMinor <= 18:
  macro parseInnerType(x: NimNode): untyped =
    newIdentNode("parse" & x[1][1].repr)
else:
  macro parseInnerType(x: typedesc): untyped =
    newIdentNode("parse" & x.getType[1][1].repr)

macro inputAsTuple(ty: untyped): untyped =
  result = nnkStmtListExpr.newTree()
  t := genSym()
  result.add quote do: (let `t` = stdin.readLine.split)
  p := nnkPar.newTree()
  for i, typ in ty.pairs:
    if typ.repr == "string":
      p.add quote do: `t`[`i`]
    else:
      parsefn := newIdentNode("parse" & typ.repr)
      p.add quote do: `t`[`i`].`parsefn`
  result.add p

template inputAsType(ty: static[typedesc]): auto =
  when ty is seq:
    when ty is seq[string]:
      stdin.readLine.split
    else:
      when NimMajor <= 0 and NimMinor <= 18:
        stdin.readLine.split.map(parseInnerType(ty.getType))
      else:
        stdin.readLine.split.map(parseInnerType(ty))
  elif ty is string:
    stdin.readLine
  elif ty is tuple:
    inputAsTuple(ty)
  else:
    stdin.readLine.`parse ty`

macro input(query: untyped): untyped =
  doAssert query.kind == nnkStmtList
  result = nnkStmtList.newTree()
  letSect := nnkLetSection.newTree()
  for defs in query:
    if defs[0].kind == nnkIdent:
      tmp := nnkIdentDefs.newTree(defs[0], newEmptyNode())
      typ := defs[1][0]
      var val: NimNode
      if typ.len <= 2:
        val = quote do: inputAsType(`typ`)
      else:
        op := typ[2]
        typ.del(2, 1)
        val = quote do: inputAsType(`typ`).mapIt(`op`)
      if defs[1].len > 1:
        op := defs[1][1]
        it := ident"it"
        tmp.add quote do: (var `it` = `val`; `op`)
      else:
        tmp.add val
      letSect.add tmp
    elif defs[0].kind == nnkPar:
      vt := nnkVarTuple.newTree()
      for id in defs[0]:
        vt.add id
      vt.add newEmptyNode()
      sle := nnkStmtListExpr.newTree()
      t := genSym()
      sle.add quote do: (let `t` = stdin.readLine.split)
      p := nnkPar.newTree()
      if defs[1][0].kind == nnkPar:
        for i, typ in defs[1][0].pairs:
          if typ.repr == "string":
            p.add quote do: `t`[`i`]
          else:
            parsefn := newIdentNode("parse" & typ.repr)
            p.add quote do: `t`[`i`].`parsefn`
      else:
        typ := defs[1][0]
        if typ.repr == "string":
          for i in 0..<defs[0].len:
            p.add quote do: `t`[`i`]
        else:
          parsefn := newIdentNode("parse" & typ.repr)
          for i in 0..<defs[0].len:
            p.add quote do: `t`[`i`].`parsefn`
      sle.add p
      vt.add sle
      letSect.add vt
    elif defs[0].kind == nnkBracketExpr:
      ids := nnkIdentDefs.newTree(defs[0][0], newEmptyNode())
      cnt := defs[0][1]
      typ := defs[1][0]
      var val: NimNode
      if typ.kind == nnkBracketExpr and typ.len > 2:
        op := typ[2]
        typ.del(2, 1)
        val = quote do: inputAsType(`typ`).mapIt(`op`)
      else:
        val = quote do: inputAsType(`typ`)
      if defs[1].len > 1:
        op := defs[1][1]
        it := ident"it"
        ids.add (quote do: newSeqWith(`cnt`, `val`).mapIt(`op`))
      else:
        ids.add (quote do: newSeqWith(`cnt`, `val`))
      letSect.add ids
  result.add letSect

#=== Template_Base =========================== }}}

#=== Template_SegmentTree ==================== {{{

type
  SegmentTree[T] = object
    n: int
    node: seq[T]
    ad: (T, T) -> T
    zero: T

proc initSegT[T](data: seq[T]; ad: (T, T) -> T; zero: T): SegmentTree[T] =
  let n = data.len.nextPowerOfTwo
  var node = newSeq[T](2*n)
  for i in range(data.len):
    node[i+n] = data[i]
  for i in range(data.len, n):
    node[i+n] = zero
  for i in countdown(n-1, 1):
    node[i] = ad(node[2*i], node[2*i+1])
  return SegmentTree[T](n: n, node: node, ad: ad, zero: zero)

proc initSegT[T](siz: int; ad: (T, T) -> T; zero: T): SegmentTree[T] =
  let n = siz.nextPowerOfTwo
  var node = newSeqWith(2*n, zero)
  return SegmentTree[T](n: n, node: node, ad: ad, zero: zero)

proc get[T](segt: SegmentTree[T]; x: int): T =
  segt.node[x + segt.n]

proc update[T](segt: var SegmentTree[T]; x: int; val: T) =
  var i = x + segt.n
  segt.node[i] = val
  i = i div 2
  while i > 0:
    segt.node[i] = segt.ad(segt.node[2*i], segt.node[2*i+1])
    i = i div 2

proc query[T](segt: SegmentTree[T]; a, b: int): T =
  if segt.n <= a or b <= 0: return segt.zero
  var
    (l, r) = (max(segt.n, a+segt.n), min(b+segt.n, segt.n * 2))
    leftVal, rightVal = segt.zero
  while l < r:
    if l mod 2 == 1:
      leftVal = segt.ad(leftVal, segt.node[l])
      l.inc
    if r mod 2 == 1:
      r.dec
      rightVal = segt.ad(segt.node[r], rightVal)
    l = l shr 1
    r = r shr 1
  return segt.ad(leftVal, rightVal)

#=== Template_SegmentTree ==================== }}}

input:
  (N, Q): int
  A: seq[int]

var segt = initSegT(zip(A, range(N)), (x, y: (int, int)) => (if x[0] < y[
    0]: x else: y), (int.high, -1))

for _ in range(Q):
  input:
    (q, l, r): int
  if q == 1:
    let (tmpl, tmpr) = (segt.get(l-1).a, segt.get(r-1).a)
    segt.update(l-1, (tmpr, l-1))
    segt.update(r-1, (tmpl, r-1))
  elif q == 2:
    echo segt.query(l-1, r).b + 1

yukicoder

結果

コンパイルメッセージ

ソースコード