結果

問題 No.2859 Falling Balls
ユーザー 👑 seekworser
提出日時 2024-08-25 16:14:36
言語 Nim
(2.2.0)
結果
AC  
実行時間 2,043 ms / 3,000 ms
コード長 16,631 bytes
コンパイル時間 5,316 ms
コンパイル使用メモリ 95,264 KB
実行使用メモリ 172,268 KB
最終ジャッジ日時 2024-08-25 16:15:13
合計ジャッジ時間 34,149 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: https://github.com/kemuniku/cplib/tree/main/src/cplib/tmpl/citrus.nim
ImportExpand "cplib/tmpl/citrus" <=== "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 import hashes\n const MODINT998244353* = 998244353\n const MODINT1000000007* = 1000000007\n
    when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 100100111.int32\n const
    INF64*: int = int(3300300300300300491)\n \n const INFL = INF64\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 =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x:
    SomeInteger, y: SomeInteger): int =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and 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 = INF64): 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 when
    not declared CPLIB_MATH_ISQRT:\n const CPLIB_MATH_ISQRT* = 1\n proc isqrt*(n: int): int =\n var x = n\n var y
    = (x + 1) shr 1\n while y < x:\n x = y\n y = (x + n div x) shr 1\n return x\n \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 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 proc
    initHashSet[T](): Hashset[T] = initHashSet[T](0)\n"
# source: https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/extra/structure/segtree_2d.nim
ImportExpand "atcoder/extra/structure/segtree_2d" <=== "when not declared ATCODER_SEGTREE_2D_HPP:\n const ATCODER_SEGTREE_2D_HPP* = 1\n when not
    declared ATCODER_SEGTREE_HPP:\n const ATCODER_SEGTREE_HPP* = 1\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 \n import std/sequtils\n import std/algorithm\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 \n \n #{.push inline.}\n type SegTree*[S; p:static[tuple]] = object\n
     len*, size*, log*:int\n d: seq[S]\n \n template calc_op*[ST:SegTree](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:SegTree](self:ST or typedesc[ST]):auto =\n block:\n let u = ST.p.e()\n
     u\n proc update[ST:SegTree](self: var ST, k:int) =\n self.d[k] = ST.calc_op(self.d[2 * k], self.d[2 * k + 1])\n \n proc init*[ST
    :SegTree](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: self.d[size + i] = v[i]\n for i in countdown(size - 1, 1): self.update(i)\n
    proc init*[ST:SegTree](self: var ST, n:int) =\n self.init(newSeqWith(n, ST.calc_e()))\n proc init*[ST:SegTree](self: typedesc[ST], v
    :seq[ST.S]):auto =\n result = ST()\n result.init(v)\n proc init*[ST:SegTree](self: typedesc[ST], n:int):auto =\n self.init
    (newSeqWith(n, ST.calc_e()))\n template SegTreeType*[S](op0, e0:untyped):typedesc[SegTree] =\n proc op1(l, r:S):S {.gensym inline.} = op0
    (l, r)\n proc e1():S {.gensym inline.} = e0()\n SegTree[S, (op:op1, e:e1)]\n template getType*(ST:typedesc[SegTree], S:typedesc, op,
    e:untyped):typedesc[SegTree] =\n SegTreeType[S](op, e)\n \n template initSegTree*[S](v:seq[S] or int, op, e:untyped):auto =\n
    SegTreeType[S](op, e).init(v)\n \n proc set*[ST:SegTree](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 self.d[p] = x\n for i in 1..self.log: self.update(p shr i)\n \n proc get*[ST:SegTree](self:ST, p
    :IndexType):ST.S =\n let p = self^^p\n assert p in 0..<self.len\n return self.d[p + self.size]\n \n proc prod*[ST:SegTree](self
    :ST, p:RangeType):ST.S =\n var (l, r) = self.halfOpenEndpoints(p)\n assert 0 <= l and l <= r and r <= self.len\n var\n sml,
    smr = ST.calc_e()\n l += self.size; r += self.size\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
    proc `[]`*[ST:SegTree](self:ST, p:IndexType):auto = self.get(p)\n proc `[]`*[ST:SegTree](self:ST, p:RangeType):auto = self.prod(p)\n proc
    `[]=`*[ST:SegTree](self:var ST, p:IndexType, x:ST.S) = self.set(p, x)\n \n proc all_prod*[ST:SegTree](self:ST):ST.S = self.d[1]\n \n # proc
    max_right*[ST:SegTree, f:static[proc(s:ST.S):bool]](self:ST, l:int):auto = self.max_right(l, f)\n proc max_right*[ST:SegTree](self:ST, l
    :IndexType, f:proc(s:ST.S):bool):int =\n var l = self^^l\n assert l in 0..self.len\n assert f(ST.calc_e())\n if l == self.len:
    return self.len\n l += self.size\n var sm = ST.calc_e()\n while true:\n while l mod 2 == 0: l = l shr 1\n if not f(ST
    .calc_op(sm, self.d[l])):\n while l < self.size:\n l = (2 * l)\n if f(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 # proc min_left*[ST:SegTree, f:static[proc(s:ST.S):bool]](self:ST, r:int):auto =
    self.min_left(r, f)\n proc min_left*[ST:SegTree](self:ST, r:IndexType, f:proc(s:ST.S):bool):int =\n var r = self^^r\n assert r in 0
    ..self.len\n assert f(ST.calc_e())\n if r == 0: return 0\n r += self.size\n var sm = ST.calc_e()\n while true:\n r
    .dec\n while r > 1 and (r mod 2 != 0): r = r shr 1\n if not f(ST.calc_op(self.d[r], sm)):\n while r < self.size:\n
     r = (2 * r + 1)\n if f(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 \n
    type SegTree2D*[S; SegTree] = object\n N2: int\n xs: seq[S]\n ys: seq[seq[S]]\n segt: seq[SegTree]\n\n proc initSegTree2D*[S](v:
    seq[tuple[x, y:int]], op: static[proc(a, b:S):S], e: static[proc():S]):auto =\n type st = SegTreeType[S](op, e)\n result = SegTree2D[S, st]
    ()\n for i in 0 ..< v.len: result.xs.add v[i].x\n result.xs.sort\n result.xs = result.xs.deduplicate(true)\n var N2 = 1\n while N2
    < result.xs.len: N2 *= 2\n\n result.ys.setLen(N2 * 2)\n result.segt.setLen(N2 * 2)\n result.N2 = N2\n\n for (x, y) in v:\n let xi
    = result.xs.lowerBound(x)\n var i = xi + result.N2\n while i > 0:\n result.ys[i].add y\n i = i shr 1\n\n for i in 1 ..<
    result.ys.len:\n result.ys[i].sort\n result.ys[i] = result.ys[i].deduplicate(true)\n result.segt[i].init(result.ys[i].len)\n\n
    proc add*[ST:SegTree2D](self: var ST, x, y:int, v:ST.S) =\n let xi = self.xs.lowerBound(x)\n doAssert self.xs[xi] == x\n var i = xi +
    self.N2\n while i > 0:\n let yi = self.ys[i].lowerBound(y)\n doAssert self.ys[i][yi] == y\n self.segt[i][yi] = self.SegTree
    .calc_op(self.segt[i][yi], v)\n i = i shr 1\n\n proc get*[ST:SegTree2D](self: var ST, x, y:int):ST.S =\n let xi = self.xs.lowerBound(x)\n
     doAssert self.xs[xi] == x\n result = self.SegTree.calc_e()\n var i = xi + self.N2\n while i > 0:\n let yi = self.ys[i].lowerBound
    (y)\n doAssert self.ys[i][yi] == y\n result = self.SegTree.calc_op(self.segt[i][yi], result)\n i = i shr 1\n proc `[]`*[ST
    :SegTree2D](self: var ST, x, y:int):ST.S = self.get(x, y)\n\n proc prod*[ST:SegTree2D](self: var ST, xp, yp: Slice[int] or int):ST.S =\n when
    xp is int:\n let xp = xp .. xp\n when yp is int:\n let yp = yp .. yp\n var\n sml, smr = self.SegTree.calc_e()\n let\n
     xl = xp.a\n xr = xp.b + 1\n yl = yp.a\n yr = yp.b + 1\n xil = self.xs.lowerBound(xl)\n xir = self.xs.lowerBound(xr)\n
     var\n l = xil + self.N2\n r = xir + self.N2\n while l < r:\n if (l and 1) != 0:\n let\n yli = self.ys[l]
    .lowerBound(yl)\n yri = self.ys[l].lowerBound(yr)\n sml = self.SegTree.calc_op(self.segt[l][yli ..< yri], sml)\n l.inc\n
     if (r and 1) != 0:\n r.dec\n let\n yli = self.ys[r].lowerBound(yl)\n yri = self.ys[r].lowerBound(yr)\n
    smr = self.SegTree.calc_op(self.segt[r][yli ..< yri], smr)\n l = l shr 1\n r = r shr 1\n return self.SegTree.calc_op(sml, smr)\n
    proc `[]`*[ST:SegTree2D](self: var ST, xp, yp: Slice[int] or int):ST.S = self.prod(xp, yp)\n"
# {.checks: off.}
var n,k = input(int)
var txc = newSeq[(int, int, int)](n)
for i in 0..<n: txc[i][0] = input(int)
for i in 0..<n: txc[i][1] = input(int)
for i in 0..<n: txc[i][2] = input(int)
txc = txc.sortedByIt(it[0])
proc op(x, y: int): int = max(x, y)
proc e(): int = -INFL
var v = @[(-INFL, -INFL), (INFL, INFL), (0, 0)]
for (t, x, _) in txc:
var l = x - k * t
var r = x + k * t
v.add((l, r))
var seg = initSegTree2D[int](v, op, e)
seg.add(0, 0, 0)
var dp = newSeqWith(n+1, -INFL)
for i in 1..n:
var (t,x,c) = txc[i-1]
dp[i].max= seg.prod(x-k*t..INFL, -INFL..x+k*t)
dp[i] += c
var l = x - k * t
var r = x + k * t
debug(t, x, c, dp[i], l, r)
var cur = seg.get(x-k*t, x+k*t)
seg.add(x-k*t, x+k*t, max(cur, dp[i]))
cur = seg.get(x-k*t, x+k*t)
print(dp.max)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0