#948313 (Nim) No.2697 Range LIS Query

提出ソース
結果

問題	No.2697 Range LIS Query
ユーザー	👑 seekworser
提出日時	2024-02-06 14:03:47
言語	Nim (2.0.2)
結果	AC
実行時間	5,048 ms / 10,000 ms
コード長	16,557 bytes
コンパイル時間	4,564 ms
コンパイル使用メモリ	93,684 KB
実行使用メモリ	49,652 KB
最終ジャッジ日時	2024-02-07 21:29:34
合計ジャッジ時間	56,800 ms
ジャッジサーバーID （参考情報）	judge15 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	1 ms 6,676 KB
testcase_03	AC	92 ms 6,676 KB
testcase_04	AC	93 ms 6,676 KB
testcase_05	AC	103 ms 6,676 KB
testcase_06	AC	4,676 ms 49,652 KB
testcase_07	AC	4,664 ms 49,652 KB
testcase_08	AC	4,751 ms 49,652 KB
testcase_09	AC	3,884 ms 49,652 KB
testcase_10	AC	3,890 ms 49,652 KB
testcase_11	AC	3,823 ms 49,652 KB
testcase_12	AC	3,313 ms 47,380 KB
testcase_13	AC	3,145 ms 45,952 KB
testcase_14	AC	3,857 ms 46,608 KB
testcase_15	AC	5,048 ms 49,652 KB
testcase_16	AC	4,921 ms 49,652 KB
testcase_17	AC	4,842 ms 49,652 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
{.checks: off.}
ImportExpand "cplib/tmpl/citrus.nim" <=== "when not declared CPLIB_TMPL_CITRUS:\n    const CPLIB_TMPL_CITRUS* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import os\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import std/math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import streams\n    import deques\n    import bitops\n    import heapqueue\n    import options\n    const MODINT998244353* = 998244353\n    const MODINT1000000007* = 1000000007\n    const INF* = 100100111\n    const INFL* = int(3300300300300300491)\n    type double* = float64\n    let readNext = iterator(getsChar: bool = false): string {.closure.} =\n        while true:\n            var si: string\n            try: si = stdin.readLine\n            except EOFError: yield \"\"\n            for s in si.split:\n                if getsChar:\n                    for i in 0..<s.len():\n                        yield s[i..i]\n                else:\n                    if s.isEmptyOrWhitespace: continue\n                    yield s\n    proc input*(t: typedesc[string]): string = readNext()\n    proc input*(t: typedesc[char]): char = readNext(true)[0]\n    proc input*(t: typedesc[int]): int = readNext().parseInt\n    proc input*(t: typedesc[float]): float = readNext().parseFloat\n    macro input*(t: typedesc, n: varargs[int]): untyped =\n        var repStr = \"\"\n        for arg in n:\n            repStr &= &\"({arg.repr}).newSeqWith \"\n        parseExpr(&\"{repStr}input({t})\")\n    macro input*(ts: varargs[auto]): untyped =\n        var tupStr = \"\"\n        for t in ts:\n            tupStr &= &\"input({t.repr}),\"\n        parseExpr(&\"({tupStr})\")\n    macro input*(n: int, ts: varargs[auto]): untyped =\n        for typ in ts:\n            if typ.typeKind != ntyAnything:\n                error(\"Expected typedesc, got \" & typ.repr, typ)\n        parseExpr(&\"({n.repr}).newSeqWith input({ts.repr})\")\n    proc `fmtprint`*(x: int or string or char or bool): string = return $x\n    proc `fmtprint`*(x: float or float32 or float64): string = return &\"{x:.16f}\"\n    proc `fmtprint`*[T](x: seq[T] or Deque[T] or HashSet[T] or set[T]): string = return x.toSeq.join(\" \")\n    proc `fmtprint`*[T, N](x: array[T, N]): string = return x.toSeq.join(\" \")\n    proc `fmtprint`*[T](x: HeapQueue[T]): string =\n        var q = x\n        while q.len != 0:\n            result &= &\"{q.pop()}\"\n            if q.len != 0: result &= \" \"\n    proc `fmtprint`*[T](x: CountTable[T]): string =\n        result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n    proc `fmtprint`*[K, V](x: Table[K, V]): string =\n        result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n    proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `fmtprint`]) =\n        for i in 0..<len(args):\n            prop.f.write(&\"{args[i]}\")\n            if i != len(args) - 1: prop.f.write(prop.sepc) else: prop.f.write(prop.endc)\n        if prop.flush: prop.f.flushFile()\n    proc print*(args: varargs[string, `fmtprint`]) = print((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n    const LOCAL_DEBUG{.booldefine.} = false\n    macro getSymbolName(x: typed): string = x.toStrLit\n    macro debug*(args: varargs[untyped]): untyped =\n        when LOCAL_DEBUG:\n            result = newNimNode(nnkStmtList, args)\n            template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n            for i, arg in args:\n                if arg.kind == nnkStrLit:\n                    result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n                else:\n                    result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n                    result.add(quote do: print(prop(), `arg`))\n                if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n                else: result.add(quote do: print(prop(), \"\\n\"))\n        else:\n            return (quote do: discard)\n    proc `%`*(x: SomeInteger, y: SomeInteger): int = (result = x mod y; if result < 0: result += y)\n    proc `//`*(x: SomeInteger, y: SomeInteger): int = (result = x div y; if result * y > x: result -= 1)\n    proc `^`*(x: SomeInteger, y: SomeInteger): int = x xor y\n    proc `&`*(x: SomeInteger, y: SomeInteger): int = x and y\n    proc `|`*(x: SomeInteger, y: SomeInteger): int = x or y\n    proc `>>`*(x: SomeInteger, y: SomeInteger): int = x shr y\n    proc `<<`*(x: SomeInteger, y: SomeInteger): int = x shl y\n    proc `%=`*(x: var SomeInteger, y: SomeInteger): void = x = x % y\n    proc `//=`*(x: var SomeInteger, y: SomeInteger): void = x = x // y\n    proc `^=`*(x: var SomeInteger, y: SomeInteger): void = x = x ^ y\n    proc `&=`*(x: var SomeInteger, y: SomeInteger): void = x = x & y\n    proc `|=`*(x: var SomeInteger, y: SomeInteger): void = x = x | y\n    proc `>>=`*(x: var SomeInteger, y: SomeInteger): void = x = x >> y\n    proc `<<=`*(x: var SomeInteger, y: SomeInteger): void = x = x << y\n    proc `[]`*(x, n: int): bool = (x and (1 shl n)) != 0\n    proc `[]=`*(x: var int, n: int, i: bool) =\n        if i: x = x or (1 << n)\n        else: (if x[n]: x = x xor (1 << n))\n    proc pow*(a, n: int, m = INFL): int =\n        var\n            rev = 1\n            a = a\n            n = n\n        while n > 0:\n            if n % 2 != 0: rev = (rev * a) mod m\n            if n > 1: a = (a * a) mod m\n            n >>= 1\n        return rev\n    proc sqrt*(x: int): int =\n        assert(x >= 0)\n        result = int(sqrt(float64(x)))\n        while result * result > x: result -= 1\n        while (result+1) * (result+1) <= x: result += 1\n    proc chmax*[T](x: var T, y: T): bool {.discardable.} = (if x < y: (x = y; return true; ) return false)\n    proc chmin*[T](x: var T, y: T): bool {.discardable.} = (if x > y: (x = y; return true; ) return false)\n    proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n    proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n    proc at*(x: char, a = '0'): int = int(x) - int(a)\n    converter tofloat*(n: int): float = float(n)\n    proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n    proc No*(b: bool = true): void = Yes(not b)\n    proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n    proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n    const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n    const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]\n    macro exit*(statement: untyped): untyped = (quote do: (`statement`; quit()))\n"
ImportExpand "atcoder/lazysegtree.nim" <=== "when not declared ATCODER_LAZYSEGTREE_HPP:\n  const ATCODER_LAZYSEGTREE_HPP* = 1\n  \n  #[ import atcoder/internal_bit ]#\n  when not declared ATCODER_INTERNAL_BITOP_HPP:\n    const ATCODER_INTERNAL_BITOP_HPP* = 1\n    import std/bitops\n  \n  #ifdef _MSC_VER\n  #include <intrin.h>\n  #endif\n  \n  # @param n `0 <= n`\n  # @return minimum non-negative `x` s.t. `n <= 2**x`\n    proc ceil_pow2*(n:SomeInteger):int =\n      var x = 0\n      while (1.uint shl x) < n.uint: x.inc\n      return x\n  # @param n `1 <= n`\n  # @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`\n    proc bsf*(n:SomeInteger):int =\n      return countTrailingZeroBits(n)\n  #[ import atcoder/rangeutils ]#\n  when not declared ATCODER_RANGEUTILS_HPP:\n    const ATCODER_RANGEUTILS_HPP* = 1\n    type RangeType* = Slice[int] | HSlice[int, BackwardsIndex] | Slice[BackwardsIndex]\n    type IndexType* = int | BackwardsIndex\n    template halfOpenEndpoints*(p:Slice[int]):(int,int) = (p.a, p.b + 1)\n    template `^^`*(s, i: untyped): untyped =\n      (when i is BackwardsIndex: s.len - int(i) else: int(i))\n    template halfOpenEndpoints*[T](s:T, p:RangeType):(int,int) =\n      (s^^p.a, s^^p.b + 1)\n  import std/sequtils\n  import std/algorithm\n  {.push inline.}\n  type LazySegTree*[S,F;p:static[tuple]] = object\n    len*, size*, log*:int\n    d*:seq[S]\n    lz*:seq[F]\n\n  template calc_op*[ST:LazySegTree](self:ST or typedesc[ST], a, b:ST.S):auto =\n    block:\n      let u = ST.p.op(a, b)\n      u\n  template calc_e*[ST:LazySegTree](self:ST or typedesc[ST]):auto =\n    block:\n      let u = ST.p.e()\n      u\n  template calc_mapping*[ST:LazySegTree](self:ST or typedesc[ST], a:ST.F, b:ST.S):auto =\n    block:\n      let u = ST.p.mapping(a, b)\n      u\n  template calc_composition*[ST:LazySegTree](self:ST or typedesc[ST], a, b:ST.F):auto =\n    block:\n      # こう書かないとバグる事象を検出\n      let u = ST.p.composition(a, b)\n      u\n  template calc_id*[ST:LazySegTree](self:ST or typedesc[ST]):auto =\n    block:\n      let u = ST.p.id()\n      u\n\n  proc update[ST:LazySegTree](self:var ST, k:int) =\n    self.d[k] = ST.calc_op(self.d[2 * k], self.d[2 * k + 1])\n  proc all_apply*[ST:LazySegTree](self:var ST, k:int, f:ST.F) =\n    self.d[k] = ST.calc_mapping(f, self.d[k])\n    if k < self.size:\n      self.lz[k] = ST.calc_composition(f, self.lz[k])\n  proc all_apply*[ST:LazySegTree](self:var ST, f:ST.F) =\n    self.all_apply(1, f)\n  proc push*[ST:LazySegTree](self: var ST, k:int) =\n    self.all_apply(2 * k, self.lz[k])\n    self.all_apply(2 * k + 1, self.lz[k])\n    self.lz[k] = ST.calc_id()\n\n  proc init[ST:LazySegTree](self:var ST, v:seq[ST.S]) =\n    let\n      n = v.len\n      log = ceil_pow2(n)\n      size = 1 shl log\n    (self.len, self.size, self.log) = (n, size, log)\n    if self.d.len < 2 * size:\n      self.d = newSeqWith(2 * size, ST.calc_e())\n    else:\n      self.d.fill(0, 2 * size - 1, ST.calc_e())\n    for i in 0..<n:\n      self.d[size + i] = v[i]\n    if self.lz.len < size:\n      self.lz = newSeqWith(size, ST.calc_id())\n    else:\n      self.lz.fill(0, size - 1, ST.calc_id())\n    for i in countdown(size - 1, 1): self.update(i)\n  proc init*[ST:LazySegTree](self: var ST, n:int) = self.init(newSeqWith(n, ST.calc_e()))\n  proc init*[ST:LazySegTree](self: typedesc[ST], v:seq[ST.S] or int):ST = result.init(v)\n\n  template LazySegTreeType[S, F](op0, e0, mapping0, composition0, id0:untyped):typedesc[LazySegTree] =\n    proc op1(a, b:S):S {.gensym inline.} = op0(a, b)\n    proc e1():S {.gensym inline.} = e0()\n    proc mapping1(f:F, s:S):S {.gensym inline.} = mapping0(f, s)\n    proc composition1(f1, f2:F):F {.gensym inline.} = composition0(f1, f2)\n    proc id1():F {.gensym inline.} = id0()\n    LazySegTree[S, F, (op:op1, e:e1, mapping:mapping1, composition:composition1, id:id1)]\n\n  template getType*(ST:typedesc[LazySegTree], S, F:typedesc, op, e, mapping, composition, id:untyped):typedesc[LazySegTree] =\n    LazySegTreeType[S, F](op, e, mapping, composition, id)\n\n  template initLazySegTree*[S, F](v:seq[S] or int, op, e, mapping, composition, id:untyped):auto =\n    LazySegTreeType[S, F](op, e, mapping, composition, id).init(v)\n\n  proc set*[ST:LazySegTree](self: var ST, p:IndexType, x:ST.S) =\n    var p = self^^p\n    assert p in 0..<self.len\n    p += self.size\n    for i in countdown(self.log, 1): self.push(p shr i)\n    self.d[p] = x\n    for i in 1..self.log: self.update(p shr i)\n\n  proc get*[ST:LazySegTree](self: var ST, p:IndexType):ST.S =\n    var p = self^^p\n    assert p in 0..<self.len\n    p += self.size\n    for i in countdown(self.log, 1): self.push(p shr i)\n    return self.d[p]\n\n  proc `[]=`*[ST:LazySegTree](self: var ST, p:IndexType, x:ST.S) = self.set(p, x)\n  proc `[]`*[ST:LazySegTree](self: var ST, p:IndexType):ST.S = self.get(p)\n\n  proc prod*[ST:LazySegTree](self:var ST, p:RangeType):ST.S =\n    var (l, r) = self.halfOpenEndpoints(p)\n    assert 0 <= l and l <= r and r <= self.len\n    if l == r: return ST.calc_e()\n\n    l += self.size\n    r += self.size\n\n    for i in countdown(self.log, 1):\n      if ((l shr i) shl i) != l: self.push(l shr i)\n      if ((r shr i) shl i) != r: self.push(r shr i)\n\n    var sml, smr = ST.calc_e()\n    while l < r:\n      if (l and 1) != 0: sml = ST.calc_op(sml, self.d[l]);l.inc\n      if (r and 1) != 0: r.dec;smr = ST.calc_op(self.d[r], smr)\n      l = l shr 1\n      r = r shr 1\n    return ST.calc_op(sml, smr)\n\n  proc `[]`*[ST:LazySegTree](self: var ST, p:RangeType):ST.S = self.prod(p)\n\n  proc all_prod*[ST:LazySegTree](self:ST):auto = self.d[1]\n\n  proc apply*[ST:LazySegTree](self: var ST, p:IndexType, f:ST.F) =\n    var p = self^^p\n    assert p in 0..<self.len\n    p += self.size\n    for i in countdown(self.log, 1): self.push(p shr i)\n    self.d[p] = ST.calc_mapping(f, self.d[p])\n    for i in 1..self.log: self.update(p shr i)\n  proc apply*[ST:LazySegTree](self: var ST, p:RangeType, f:ST.F) =\n    var (l, r) = self.halfOpenEndpoints(p)\n    assert 0 <= l and l <= r and r <= self.len\n    if l == r: return\n\n    l += self.size\n    r += self.size\n\n    for i in countdown(self.log, 1):\n      if ((l shr i) shl i) != l: self.push(l shr i)\n      if ((r shr i) shl i) != r: self.push((r - 1) shr i)\n\n    block:\n      var (l, r) = (l, r)\n      while l < r:\n        if (l and 1) != 0: self.all_apply(l, f);l.inc\n        if (r and 1) != 0: r.dec;self.all_apply(r, f)\n        l = l shr 1\n        r = r shr 1\n\n    for i in 1..self.log:\n      if ((l shr i) shl i) != l: self.update(l shr i)\n      if ((r shr i) shl i) != r: self.update((r - 1) shr i)\n\n#  template <bool (*g)(S)> int max_right(int l) {\n#    return max_right(l, [](S x) { return g(x); });\n#  }\n  proc max_right*[ST:LazySegTree](self:var ST, l:IndexType, g:proc(s:ST.S):bool):int =\n    var l = self^^l\n    assert l in 0..self.len\n    assert g(ST.calc_e())\n    if l == self.len: return self.len\n    l += self.size\n    for i in countdown(self.log, 1): self.push(l shr i)\n    var sm = ST.calc_e()\n    while true:\n      while l mod 2 == 0: l = l shr 1\n      if not g(ST.calc_op(sm, self.d[l])):\n        while l < self.size:\n          self.push(l)\n          l = (2 * l)\n          if g(ST.calc_op(sm, self.d[l])):\n            sm = ST.calc_op(sm, self.d[l])\n            l.inc\n        return l - self.size\n      sm = ST.calc_op(sm, self.d[l])\n      l.inc\n      if not((l and -l) != l): break\n    return self.len\n\n#  template <bool (*g)(S)> int min_left(int r) {\n#    return min_left(r, [](S x) { return g(x); });\n#  }\n  proc min_left*[ST:LazySegTree](self: var ST, r:IndexType, g:proc(s:ST.S):bool):int =\n    var r = self^^r\n    assert r in 0..self.len\n    assert(g(ST.calc_e()))\n    if r == 0: return 0\n    r += self.size\n    for i in countdown(self.log, 1): self.push((r - 1) shr i)\n    var sm = ST.calc_e()\n    while true:\n      r.dec\n      while r > 1 and r mod 2 == 1: r = r shr 1\n      if not g(ST.calc_op(self.d[r], sm)):\n        while r < self.size:\n          self.push(r)\n          r = (2 * r + 1)\n          if g(ST.calc_op(self.d[r], sm)):\n            sm = ST.calc_op(self.d[r], sm)\n            r.dec\n        return r + 1 - self.size\n      sm = ST.calc_op(self.d[r], sm)\n      if not ((r and -r) != r): break\n    return 0\n  {.pop.}\n"

var lr = collect(newSeq):
    for i in 0..<4:
        for j in i..<4:
            (i, j)
var lri = (block:
    (proc(): Table[(int, int), int] =
        for i, (l, r) in lr:
            result[(l, r)] = i
    )()
)
proc op(x, y: (seq[int], int)): (seq[int], int) =
    var n = x[0].len
    var rseq = (0..<lr.len).toSeq.mapIt(max(x[0][it], y[0][it]))
    for i in 0..<lr.len:
        var (l, k) = lr[i]
        for r in k..<4:
            rseq[lri[(l, r)]].max = x[0][i] + y[0][lri[(k, r)]]
    return (rseq, x[1] + y[1])
proc e(): (seq[int], int) = (newSeqWith(lr.len, 0), 0)
proc mapping(f: int, x: (seq[int], int)): (seq[int], int) =
    if f == INFL: return x
    var rseq = newSeqWith(lr.len, 0)
    for i in 0..<lr.len:
        var (l, r) = lr[i]
        if l <= f and r >= f:
            rseq[lri[(l, r)]] = x[1]
    return (rseq, x[1])
proc composition(f, g: int): int = (if f == INFL: g else: f)
proc id(): int = INFL

var n = input(int)
var a = input(int, n).mapIt(it-1)
var lseg = initLazySegTree[(seq[int], int), int](newSeqWith(n, (newSeqWith(lr.len, 0), 1)), op, e, mapping, composition, id)
for i in 0..<n: lseg.apply(i..i, a[i])

var q = input(int)
for _ in 0..<q:
    var t = input(int)
    if t == 1:
        var l, r = input(int)
        print(lseg.prod(l-1..<r)[0].max)
    else:
        var l, r, x = input(int)
        lseg.apply(l-1..<r, x-1)
yukicoder

結果

テストケース

ソースコード
