#712600 (Nim) No.1705 Mode of long array

提出ソース

結果

問題	No.1705 Mode of long array
ユーザー	yuly3
提出日時	2021-11-03 14:52:56
言語	Nim (2.0.2)
結果	AC
実行時間	131 ms / 3,000 ms
コード長	9,487 bytes
コンパイル時間	3,684 ms
コンパイル使用メモリ	74,180 KB
実行使用メモリ	12,416 KB
最終ジャッジ日時	2024-04-21 05:54:06
合計ジャッジ時間	11,410 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	7 ms 5,376 KB
testcase_08	AC	6 ms 5,376 KB
testcase_09	AC	5 ms 5,376 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	5 ms 5,376 KB
testcase_13	AC	92 ms 9,088 KB
testcase_14	AC	65 ms 6,272 KB
testcase_15	AC	63 ms 5,376 KB
testcase_16	AC	74 ms 5,376 KB
testcase_17	AC	55 ms 5,376 KB
testcase_18	AC	45 ms 5,376 KB
testcase_19	AC	84 ms 5,376 KB
testcase_20	AC	54 ms 5,376 KB
testcase_21	AC	73 ms 8,916 KB
testcase_22	AC	105 ms 9,388 KB
testcase_23	AC	65 ms 5,376 KB
testcase_24	AC	69 ms 5,376 KB
testcase_25	AC	67 ms 5,376 KB
testcase_26	AC	67 ms 5,376 KB
testcase_27	AC	67 ms 5,376 KB
testcase_28	AC	66 ms 5,376 KB
testcase_29	AC	69 ms 5,376 KB
testcase_30	AC	69 ms 5,376 KB
testcase_31	AC	69 ms 5,376 KB
testcase_32	AC	69 ms 5,376 KB
testcase_33	AC	125 ms 8,700 KB
testcase_34	AC	123 ms 8,704 KB
testcase_35	AC	125 ms 8,512 KB
testcase_36	AC	127 ms 8,512 KB
testcase_37	AC	130 ms 8,704 KB
testcase_38	AC	130 ms 8,488 KB
testcase_39	AC	129 ms 8,760 KB
testcase_40	AC	129 ms 8,576 KB
testcase_41	AC	129 ms 8,576 KB
testcase_42	AC	131 ms 8,620 KB
testcase_43	AC	86 ms 12,288 KB
testcase_44	AC	88 ms 12,416 KB
testcase_45	AC	88 ms 12,176 KB
testcase_46	AC	89 ms 12,312 KB
testcase_47	AC	89 ms 12,380 KB
testcase_48	AC	87 ms 12,288 KB
testcase_49	AC	123 ms 9,344 KB
testcase_50	AC	121 ms 9,228 KB
testcase_51	AC	123 ms 9,280 KB
testcase_52	AC	128 ms 9,216 KB
testcase_53	AC	125 ms 9,344 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

/home/judge/data/code/Main.nim(13, 5) Warning: imported and not used: 'strformat' [UnusedImport]

ソースコード

raw source code

when not declared ATCODER_YULY3HEADER_HPP:
  const ATCODER_YULY3HEADER_HPP* = 1

  import
    algorithm,
    bitops,
    deques,
    heapqueue,
    math,
    macros,
    sets,
    sequtils,
    strformat,
    strutils,
    sugar,
    tables

  proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
    # Looks for the last statement of the last statement, etc...
    case n.kind
    of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      for i in ord(n.kind == nnkCaseStmt)..<n.len:
        (result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
    of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
        nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      if n.len >= 1:
        (result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],
            res, bracketExpr)
    of nnkTableConstr:
      result[1] = n[0][0]
      result[2] = n[0][1]
      if bracketExpr.len == 1:
        bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
            bindSym"typeof", newEmptyNode())])
      template adder(res, k, v) = res[k] = v
      result[0] = getAst(adder(res, n[0][0], n[0][1]))
    of nnkCurly:
      result[2] = n[0]
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.incl(v)
      result[0] = getAst(adder(res, n[0]))
    else:
      result[2] = n
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.add(v)
      result[0] = getAst(adder(res, n))

  macro collect*(init, body: untyped): untyped =
    runnableExamples:
      import sets, tables
      let data = @["bird", "word"]
      ## seq:
      let k = collect(newSeq):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert k == @["bird"]
      ## seq with initialSize:
      let x = collect(newSeqOfCap(4)):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert x == @["bird"]
      ## HashSet:
      let y = initHashSet.collect:
        for d in data.items: {d}
      assert y == data.toHashSet
      ## Table:
      let z = collect(initTable(2)):
        for i, d in data.pairs: {i: d}
      assert z == {0: "bird", 1: "word"}.toTable

    let res = genSym(nskVar, "collectResult")
    expectKind init, {nnkCall, nnkIdent, nnkSym}
    let bracketExpr = newTree(nnkBracketExpr,
      if init.kind == nnkCall: init[0] else: init)
    let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
    if bracketExpr.len == 3:
      bracketExpr[1][1] = keyType
      bracketExpr[2][1] = valueType
    else:
      bracketExpr[1][1] = valueType
    let call = newTree(nnkCall, bracketExpr)
    if init.kind == nnkCall:
      for i in 1 ..< init.len:
        call.add init[i]
    result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)

  proc nextString*(f: auto = stdin): string =
    var get = false
    result = ""
    while true:
      let c = f.readChar
      if c.int > ' '.int:
        get = true
        result.add(c)
      elif get: return
  proc nextInt*(f: auto = stdin): int = parseInt(f.nextString)
  proc nextFloat*(f: auto = stdin): float = parseFloat(f.nextString)

  proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)
  proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)
  proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)
  proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or m
  proc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and m
  proc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor m
  proc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl m
  proc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr m

when not declared ATCODER_INTERNAL_BITOP_HPP:
  const ATCODER_INTERNAL_BITOP_HPP* = 1

  proc ceil_pow2*(n: SomeInteger): int =
    var x = 0
    while (1.uint shl x) < n.uint: x.inc
    return x

  proc bsf*(n: SomeInteger): int =
    return countTrailingZeroBits(n)

when not declared ATCODER_RANGEUTILS_HPP:
  const ATCODER_RANGEUTILS_HPP* = 1
  type RangeType* = Slice[int] | HSlice[int, BackwardsIndex]
  type IndexType* = int | BackwardsIndex
  template halfOpenEndpoints*(p: Slice[int]): (int, int) = (p.a, p.b + 1)
  template `^^`*(s, i: untyped): untyped =
    (when i is BackwardsIndex: s.len - int(i) else: int(i))
  template halfOpenEndpoints*[T](s: T, p: RangeType): (int, int) =
    (p.a, s^^p.b + 1)

when not declared ATCODER_SEGTREE_HPP:
  const ATCODER_SEGTREE_HPP* = 1

  {.push inline.}
  type SegTree*[S; p: static[tuple]] = object
    len*, size*, log*: int
    d: seq[S]

  template calc_op[ST: SegTree](self: typedesc[ST], a, b: ST.S): auto =
    block:
      let op = ST.p.op
      op(a, b)
  template calc_e[ST: SegTree](self: typedesc[ST]): auto =
    block:
      let e = ST.p.e
      e()
  proc update[ST: SegTree](self: var ST, k: int) =
    self.d[k] = ST.calc_op(self.d[2 * k], self.d[2 * k + 1])

  proc init*[ST: SegTree](self: var ST, v: seq[ST.S]) =
    let
      n = v.len
      log = ceil_pow2(n)
      size = 1 shl log
    (self.len, self.size, self.log) = (n, size, log)
    if self.d.len < 2 * size:
      self.d = newSeqWith(2 * size, ST.calc_e())
    else:
      self.d.fill(0, 2 * size - 1, ST.calc_e())
    for i in 0..<n: self.d[size + i] = v[i]
    for i in countdown(size - 1, 1): self.update(i)
  proc init*[ST: SegTree](self: var ST, n: int) =
    self.init(newSeqWith(n, ST.calc_e()))
  proc init*[ST: SegTree](self: typedesc[ST], v: seq[ST.S]): auto =
    result = ST()
    result.init(v)
  proc init*[ST: SegTree](self: typedesc[ST], n: int): auto =
    self.init(newSeqWith(n, ST.calc_e()))
  template getType*(ST: typedesc[SegTree], S: typedesc, op0: static[(S, S)->S],
      e0: static[()->S]): typedesc[SegTree] =
    SegTree[S, (op: op0, e: e0)]
  template SegTreeType*(S: typedesc, op0: static[(S, S)->S], e0: static[()->S]): typedesc[SegTree] =
    SegTree[S, (op: op0, e: e0)]
  proc initSegTree*[S](v: seq[S], op: static[(S, S)->S], e: static[()->S]): auto =
    SegTreeType(S, op, e).init(v)
  proc initSegTree*[S](n: int, op: static[(S, S)->S], e: static[()->S]): auto =
    result = SegTreeType(S, op, e)()
    result.init(newSeqWith(n, result.type.calc_e()))

  proc set*[ST: SegTree](self: var ST, p: IndexType, x: ST.S) =
    var p = self^^p
    assert p in 0..<self.len
    p += self.size
    self.d[p] = x
    for i in 1..self.log: self.update(p shr i)

  proc get*[ST: SegTree](self: ST, p: IndexType): ST.S =
    let p = self^^p
    assert p in 0..<self.len
    return self.d[p + self.size]

  proc prod*[ST: SegTree](self: ST, p: RangeType): ST.S =
    var (l, r) = self.halfOpenEndpoints(p)
    assert 0 <= l and l <= r and r <= self.len
    var
      sml, smr = ST.calc_e()
    l += self.size; r += self.size
    while l < r:
      if (l and 1) != 0: sml = ST.calc_op(sml, self.d[l]); l.inc
      if (r and 1) != 0: r.dec; smr = ST.calc_op(self.d[r], smr)
      l = l shr 1
      r = r shr 1
    return ST.calc_op(sml, smr)
  proc `[]`*[ST: SegTree](self: ST, p: IndexType): auto = self.get(p)
  proc `[]`*[ST: SegTree](self: ST, p: RangeType): auto = self.prod(p)
  proc `[]=`*[ST: SegTree](self: var ST, p: IndexType, x: ST.S) = self.set(p, x)

  proc all_prod*[ST: SegTree](self: ST): ST.S = self.d[1]

  proc max_right*[ST: SegTree](self: ST, l: IndexType, f: proc(
      s: ST.S): bool): int =
    var l = self^^l
    assert l in 0..self.len
    assert f(ST.calc_e())
    if l == self.len: return self.len
    l += self.size
    var sm = ST.calc_e()
    while true:
      while l mod 2 == 0: l = l shr 1
      if not f(ST.calc_op(sm, self.d[l])):
        while l < self.size:
          l = (2 * l)
          if f(ST.calc_op(sm, self.d[l])):
            sm = ST.calc_op(sm, self.d[l])
            l.inc
        return l - self.size
      sm = ST.calc_op(sm, self.d[l])
      l.inc
      if not ((l and -l) != l): break
    return self.len

  proc min_left*[ST: SegTree](self: ST, r: IndexType, f: proc(
      s: ST.S): bool): int =
    var r = self^^r
    assert r in 0..self.len
    assert f(ST.calc_e())
    if r == 0: return 0
    r += self.size
    var sm = ST.calc_e()
    while true:
      r.dec
      while r > 1 and (r mod 2 != 0): r = r shr 1
      if not f(ST.calc_op(self.d[r], sm)):
        while r < self.size:
          r = (2 * r + 1)
          if f(ST.calc_op(self.d[r], sm)):
            sm = ST.calc_op(self.d[r], sm)
            r.dec
        return r + 1 - self.size
      sm = ST.calc_op(self.d[r], sm)
      if not ((r and -r) != r): break
    return 0
  {.pop.}

when isMainModule:
  let N, M = nextInt()
  var initSeq = newSeq[tuple[cnt, val: int]](M + 1)
  for i in 1..M:
    initSeq[i] = (nextInt(), i)

  proc op(x, y: tuple[cnt, val: int]): tuple[cnt, val: int] = max(x, y)
  var segt = initSegTree(initSeq, op, () => (0, 0))

  var ans: seq[int]
  let Q = nextInt()
  for _ in 0..<Q:
    let ti, xi, yi = nextInt()
    case ti
    of 1:
      segt[xi] = (segt[xi].cnt + yi, xi)
    of 2:
      segt[xi] = (segt[xi].cnt - yi, xi)
    else:
      ans.add(segt.all_prod().val)
  echo ans.join("\n")

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード