結果
| 問題 | No.3017 交互浴 |
| ユーザー |
 kemuniku
|
| 提出日時 | 2025-01-25 13:09:04 |
| 言語 | Nim (2.2.0) |
| 結果 |
AC
|
| 実行時間 | 545 ms / 2,000 ms |
| コード長 | 17,522 bytes |
| コンパイル時間 | 5,408 ms |
| コンパイル使用メモリ | 76,288 KB |
| 実行使用メモリ | 13,568 KB |
| 最終ジャッジ日時 | 2025-01-25 22:34:47 |
| 合計ジャッジ時間 | 30,629 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 55 |
コンパイルメッセージ
Hint: used config file '/home/linuxbrew/.linuxbrew/Cellar/nim/2.2.0/nim/config/nim.cfg' [Conf] Hint: used config file '/home/linuxbrew/.linuxbrew/Cellar/nim/2.2.0/nim/config/config.nims' [Conf] ............................................................................................ /home/judge/data/code/Main.nim(8, 8) Hint: duplicate import of 'options'; previous import here: (169, 12) [DuplicateModuleImport] (6, 12) Hint: duplicate import of 'sequtils'; previous import here: (170, 12) [DuplicateModuleImport] ..... (8, 12) Hint: duplicate import of 'macros'; previous import here: /home/judge/data/code/Main.nim(1, 8) [DuplicateModuleImport] ... (11, 12) Hint: duplicate import of 'strutils'; previous import here: (171, 12) [DuplicateModuleImport] ....... (19, 12) Hint: duplicate import of 'options'; previous import here: /home/judge/data/code/Main.nim(8, 8) [DuplicateModuleImport] Hint: g++ -c -std=gnu++17 -funsigned-char -w -fmax-errors=3 -fpermissive -pthread -O3 -fno-strict-aliasing -fno-ident -fno-math-errno -I/home/linuxbrew/.linuxbrew/Cellar/nim/2.2.0/nim/lib -I/home/judge/data/code -o /home/judge/.cache/nim/Main_r/@m..@s..@s..@slinuxbrew@s.linuxbrew@sCellar@snim@s2.2.0@snim@slib@ssystem@sexceptions.nim.cpp.o /home/judge/.cache/nim/Main_r/@m..@s..@s..@slinuxbrew@s.linuxbrew@sCellar@snim@s2.2.0@snim@slib@ssystem@sexceptions.nim.cpp [Exec] Hint: g++ -c -std=gnu++17 -funsigned-char -w -fmax-errors=3 -fpermissive -pthread -O3 -fno-strict-aliasing -fno-ident -fno-math-errno -I/home/linuxbrew/.linuxbrew/Cellar/nim/2.2.0/nim/lib -I/home/judge/data/code -o /home/judge/.cache/nim/Main_r/@m..@s..@s..@slinuxbrew@s.linuxbrew@sCellar@snim@s2.2.0@snim@slib@sstd@sprivate@sdigitsutils.nim.cpp.o /home/judge/.cache/nim/Main_r/@m..@s..@s..@slinuxbrew@s.linuxbrew@sCellar@snim@s2.2.0@snim@slib@sstd@sprivate@sdigitsutils.nim.cpp [Exec] Hint: g++ -c -std=gnu++17 -funsigned-char -w -fmax-errors=3 -fpermissive -pthread -O3 -fno-strict-aliasing -fno-ident -fno-math-errno -I/
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
when not defined(second_compile):
const tmp = staticExec("nim cpp -d:danger --mm:refc -o:a.out -d:second_compile Main.nim")
static:
echo tmp
quit()
ImportExpand "cplib/collections/avlset.nim" <=== "when not declared CPLIB_COLLECTIONS_AVLSET:\n const CPLIB_COLLECTIONS_AVLSET* = 1\n #[ import cplib/collections/avltreenode ]#\n when not declared CPLIB_COLLECTIONS_AVLTREE:\n const CPLIB_COLLECTIONS_AVLTREE* = 1\n when compileOption(\"mm\", \"orc\") or compileOption(\"mm\", \"arc\"):\n {.fatal: \"Plese Use refc\".}\n # 以下をNimに移植\n # https://nachiavivias.github.io/cp-library/cpp/array/bbst-list.html\n type AvlTreeNode*[K] = ref object\n l*, r*, p*: AvlTreeNode[K]\n h*, len*: int\n key*: K\n proc get_avltree_nilnode*[K](): AvlTreeNode[K] =\n let nil_node {.global.} = (block:\n var nil_node = AvlTreeNode[K](h: 0, len: 0)\n nil_node.l = nil_node\n nil_node.r = nil_node\n nil_node.p = nil_node\n nil_node\n )\n return nil_node\n proc update[K](node: AvlTreeNode[K]) =\n node.h = max(node.l.h + 1, node.r.h + 1)\n node.len = 1 + node.l.len + node.r.len\n proc set_children[K](node, l, r: AvlTreeNode[K]) =\n node.l = l\n if l != get_avltree_nilnode[K](): l.p = node\n node.r = r\n if r != get_avltree_nilnode[K](): r.p = node\n node.update()\n proc rebalance[K](node: AvlTreeNode[K]): AvlTreeNode[K] =\n var node = node\n var l = node.l\n var r = node.r\n if l.h + 1 < r.h:\n var rl = r.l\n var rr = r.r\n if rl.h <= rr.h:\n r.p = node.p\n node.set_children(l, rl)\n r.set_children(node, rr)\n return r\n else:\n rl.p = node.p\n node.set_children(l, rl.l)\n r.set_children(rl.r, rr)\n rl.set_children(node, r)\n return rl\n elif r.h + 1 < l.h:\n var ll = l.l\n var lr = l.r\n if lr.h <= ll.h:\n l.p = node.p\n node.set_children(lr, r)\n l.set_children(ll, node)\n return l\n else:\n lr.p = node.p\n node.set_children(lr.r, r)\n l.set_children(ll, lr.l)\n lr.set_children(l, node)\n return lr\n node.update\n return node\n proc rebalance_to_root[K](node: AvlTreeNode[K]): AvlTreeNode[K] =\n var node = node\n while node.p != get_avltree_nilnode[K]():\n var cp = node.p\n if cp.l == node: cp.l = node.rebalance\n else: cp.r = node.rebalance\n node = cp\n return node.rebalance\n proc rootOf*[K](node: AvlTreeNode[K]): AvlTreeNode[K] =\n result = node\n while result.p != get_avltree_nilnode[K](): result = result.p\n proc node_search[K](node: AvlTreeNode[K], key: K, strict: bool): (AvlTreeNode[K], AvlTreeNode[K]) =\n var node = node\n var result_l = get_avltree_nilnode[K]()\n var result_r = get_avltree_nilnode[K]()\n while node != get_avltree_nilnode[K]():\n if (strict and key < node.key) or (not strict and key <= node.key):\n result_r = node\n node = node.l\n else:\n result_l = node\n node = node.r\n return (result_l, result_r)\n proc lower_bound_node*[K](node: AvlTreeNode[K], key: K): (AvlTreeNode[K], AvlTreeNode[K]) = node_search[K](node, key, false)\n proc upper_bound_node*[K](node: AvlTreeNode[K], key: K): (AvlTreeNode[K], AvlTreeNode[K]) = node_search[K](node, key, true)\n proc insert*[K](node, x: AvlTreeNode[K]): AvlTreeNode[K] =\n if node == get_avltree_nilnode[K](): return x\n var (ql, qr) = node.lower_bound_node(x.key)\n if ql != get_avltree_nilnode[K]() and ql.r == get_avltree_nilnode[K]():\n ql.set_children(ql.l, x)\n return ql.rebalance_to_root\n qr.set_children(x, qr.r)\n return qr.rebalance_to_root\n proc erase*[K](node, x, nxt: AvlTreeNode[K]): AvlTreeNode[K] =\n var xp = x.p\n result = get_avltree_nilnode[K]()\n if x.r == get_avltree_nilnode[K]():\n var xl = x.l\n if xl != get_avltree_nilnode[K](): xl.p = xp\n if xp != get_avltree_nilnode[K]():\n if xp.l == x: xp.l = xl\n else: xp.r = xl\n if xp == get_avltree_nilnode[K](): result = xl\n else: result = xp.rebalance_to_root\n else:\n var nxtp = nxt.p\n var nxtr = nxt.r\n if xp != get_avltree_nilnode[K]():\n if xp.l == x: xp.l = nxt\n else: xp.r = nxt\n nxt.p = xp\n nxt.l = x.l\n if nxt.l != get_avltree_nilnode[K](): nxt.l.p = nxt\n if x.r == nxt:\n nxt.update\n result = nxt.rebalance_to_root\n else:\n if nxtp.l == nxt: nxtp.l = nxtr\n else: nxtp.r = nxtr\n if nxtr != get_avltree_nilnode[K](): nxtr.p = nxtp\n nxt.r = x.r\n nxt.r.p = nxt\n nxt.update\n result = nxtp.rebalance_to_root\n x.l = get_avltree_nilnode[K]()\n x.r = get_avltree_nilnode[K]()\n x.p = get_avltree_nilnode[K]()\n x.update\n proc next*[K](node: AvlTreeNode[K]): AvlTreeNode[K] =\n var node = node\n if node.r != get_avltree_nilnode[K]():\n node = node.r\n while node.l != get_avltree_nilnode[K](): node = node.l\n return node\n while node.p.r == node: node = node.p\n return node.p\n proc prev*[K](node: AvlTreeNode[K]): AvlTreeNode[K] =\n var node = node\n if node.l != get_avltree_nilnode[K]():\n node = node.l\n while node.r != get_avltree_nilnode[K](): node = node.r\n return node\n while node.p.l == node: node = node.p\n return node.p\n proc get*[K](node: AvlTreeNode[K], idx: int): AvlTreeNode[K] =\n assert idx >= 0\n if idx >= node.len: return get_avltree_nilnode[K]()\n result = node\n var idx = idx\n while result.l.len != idx:\n if result.l.len < idx:\n idx -= result.l.len + 1\n result = result.r\n else:\n result = result.l\n proc index*[K](node: AvlTreeNode[K]): int =\n var node = node\n if node == get_avltree_nilnode[K](): return 0\n result = node.l.len\n while node.p != get_avltree_nilnode[K]():\n if node.p.r == node: result += node.p.l.len + 1\n node = node.p\n \n import options\n import sequtils\n import strutils\n\n type AvlSortedMultiSet*[T] = object\n root*: AvlTreeNode[T]\n \n type AVLSortedSet*[T] = object\n root*: AvlTreeNode[T]\n \n type AVLSets[T] = AvlSortedMultiSet[T] or AVLSortedSet[T]\n\n proc len*[T](self: AVLSets[T]): int = self.root.len\n proc lowerBound*[T](self: AVLSets[T], x: T): int =\n var (ql, qr) = self.root.lower_bound_node(x)\n if qr == get_avltree_nilnode[T](): return self.len\n return qr.index\n proc index*[T](self: AVLSets[T], x: T): int = self.lowerBound(x)\n proc upperBound*[T](self: AVLSets[T], x: T): int =\n var (ql, qr) = self.root.upper_bound_node(x)\n if qr == get_avltree_nilnode[T](): return self.len\n return qr.index\n proc index_right*[T](self: AVLSets[T], x: T): int = self.upperBound(x)\n proc count*[T](self: AVLSets[T], x: T): int = self.upperBound(x) - self.lowerBound(x)\n proc newnode[T](x: T): AvlTreeNode[T] =\n var nil_node = get_avltree_nilnode[T]()\n return AvlTreeNode[T](p: nil_node, l: nil_node, r: nil_node, len: 1, h: 1, key: x)\n proc lt*[T](self: AVLSets[T], x: T): Option[T] =\n var (node, _) = self.root.lower_bound_node(x)\n if node == get_avltree_nilnode[T](): return none(T)\n return some(node.key)\n proc le*[T](self: AVLSets[T], x: T): Option[T] =\n var (node, _) = self.root.upper_bound_node(x)\n if node == get_avltree_nilnode[T](): return none(T)\n return some(node.key)\n proc gt*[T](self: AVLSets[T], x: T): Option[T] =\n var (_, node) = self.root.upper_bound_node(x)\n if node == get_avltree_nilnode[T](): return none(T)\n return some(node.key)\n proc ge*[T](self: AVLSets[T], x: T): Option[T] =\n var (_, node) = self.root.lower_bound_node(x)\n if node == get_avltree_nilnode[T](): return none(T)\n return some(node.key)\n proc contains*[T](self: AVLSets[T], x: T): bool =\n var (_, node) = self.root.lower_bound_node(x)\n return node != get_avltree_nilnode[T]() and node.key == x\n proc incl*[T](self: var AVLSortedMultiSet[T], x: T) =\n var node = newnode(x)\n self.root = self.root.insert(node)\n proc incl*[T](self: var AVLSortedSet[T], x: T):bool {.discardable.} =\n if self.contains(x): return false\n var node = newnode(x)\n self.root = self.root.insert(node)\n return true\n proc excl*[T](self: var AVLSets[T], x: T): bool {.discardable.} =\n if x notin self: return false\n var (_, node) = self.root.lower_bound_node(x)\n self.root = self.root.erase(node, node.next)\n return true\n proc `[]`*[T](self: AVLSets[T], idx: int): T =\n assert idx < self.root.len\n return self.root.get(idx).key\n proc `[]`*[T](self: AVLSets[T], idx: BackwardsIndex): T =\n var idx = self.len - int(idx)\n return self[idx]\n proc pop*[T](self: var AVLSets[T], idx: int = -1): T =\n var idx = idx\n if idx < 0: idx = self.len + idx\n assert idx < self.root.len\n var node = self.root.get(idx)\n result = node.key\n self.root = self.root.erase(node, node.next)\n iterator items*[T](self: AVLSets[T]): T =\n var stack = @[(0, self.root)]\n while stack.len > 0:\n var (t, node) = stack.pop\n if t == 0:\n stack.add((1, node))\n if node.l != get_avltree_nilnode[T](): stack.add((0, node.l))\n elif t == 1:\n yield node.key\n if node.r != get_avltree_nilnode[T](): stack.add((0, node.r))\n proc `$`*[T](self: AVLSets[T]): string = self.toSeq.join(\" \")\n proc initAvlSortedMultiSet*[T](v: seq[T] = @[]): AvlSortedMultiSet[T] =\n result = AvlSortedMultiSet[T](root: get_avltree_nilnode[T]())\n for item in v: result.incl(item)\n proc initAvlSortedSet*[T](v: seq[T] = @[]): AvlSortedSet[T] =\n result = AvlSortedSet[T](root: get_avltree_nilnode[T]())\n for item in v: result.incl(item)\n"
import options
type RangeSet*[T] = ref object
st* : AVLSortedMultiSet[(int,int,T)]
default* : T
proc initRangeSet*[T](default:T):RangeSet[T]=
return RangeSet[T](st:initAvlSortedMultiSet[(int,int,T)](@[(low(int),high(int),default)]),default:default)
var now = 0
proc update*[T](self:RangeSet[T],l,r:int,value:T)=
#まず、[l,r)が完全に内包している区間について消去する
var l = l
var r = r
while true:
var x = self.st.ge((l,low(int),self.default))
if x.isNone():
break
var (a,b,c) = x.get()
if b <= r:
discard self.st.excl((a,b,c))
now -= (b-a)*c
elif a < r:
#区間の右で被っているような場合
self.st.excl((a,b,c))
now -= (b-a)*c
if c == value:
r = b
else:
self.st.incl((r,b,c))
now += (b-r)*c
break
else:
if a == r and c == value:
self.st.excl((a,b,c))
now -= (b-a)*c
r = b
break
var x = self.st.le((l,high(int),self.default))
if x.issome():
var (a,b,c) = x.get()
if r < b:
if c != value:
self.st.excl((a,b,c))
now -= (b-a)*c
self.st.incl((a,l,c))
now += (l-a)*c
self.st.incl((r,b,c))
now += (b-r)*c
else:
return
elif l < b:
if c != value:
self.st.excl((a,b,c))
now -= (b-a)*c
self.st.incl((a,l,c))
now += (l-a)*c
else:
self.st.excl((a,b,c))
now -= (b-a)*c
l = a
elif l == b:
if c == value:
self.st.excl((a,b,c))
now -= (b-a)*c
l = a
self.st.incl((l,r,value))
now += (r-l)*value
proc get_segment*[T](self:RangeSet[T],x:int):(int,int,int)=
#これ最大値区間が編集されているときにバグります
self.st.le((x,high(int),self.default)).get()
ImportExpand "cplib/tmpl/sheep.nim" <=== "when not declared CPLIB_TMPL_SHEEP:\n const CPLIB_TMPL_SHEEP* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import algorithm\n import sequtils\n import tables\n import macros\n import math\n import sets\n import strutils\n import strformat\n import sugar\n import heapqueue\n import streams\n import deques\n import bitops\n import std/lenientops\n import options\n #入力系\n proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n proc si(): string {.inline.} =\n result = \"\"\n var c: char\n while true:\n c = getchar()\n if c == ' ' or c == '\\n' or c == '\\255':\n break\n result &= c\n #chmin,chmax\n template `max=`(x, y) = x = max(x, y)\n template `min=`(x, y) = x = min(x, y)\n #bit演算\n proc `%`*(x: int, y: int): 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: int, y: int): int{.inline.} =\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: var int, y: int): void = x = x%y\n proc `//=`(x: var int, y: int): void = x = x//y\n proc `**`(x: int, y: int): int = x^y\n proc `**=`(x: var int, y: int): void = x = x^y\n proc `^`(x: int, y: int): int = x xor y\n proc `|`(x: int, y: int): int = x or y\n proc `&`(x: int, y: int): int = x and y\n proc `>>`(x: int, y: int): int = x shr y\n proc `<<`(x: int, y: int): int = x shl y\n proc `~`(x: int): int = not x\n proc `^=`(x: var int, y: int): void = x = x ^ y\n proc `&=`(x: var int, y: int): void = x = x & y\n proc `|=`(x: var int, y: int): void = x = x | y\n proc `>>=`(x: var int, y: int): void = x = x >> y\n proc `<<=`(x: var int, y: int): void = x = x << y\n proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n #便利な変換\n proc `!`(x: char, a = '0'): int = int(x)-int(a)\n #定数\n #[ include cplib/utils/constants ]#\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 const INF = INF64\n #converter\n\n #range\n iterator range(start: int, ends: int, step: int): int =\n var i = start\n if step < 0:\n while i > ends:\n yield i\n i += step\n elif step > 0:\n while i < ends:\n yield i\n i += step\n iterator range(ends: int): int = (for i in 0..<ends: yield i)\n iterator range(start: int, ends: int): int = (for i in\n start..<ends: yield i)\n\n #joinが非stringでめちゃくちゃ遅いやつのパッチ\n proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n proc dump[T](arr:seq[seq[T]])=\n for i in 0..<len(arr):\n echo arr[i]\n"
var N = ii()
var H = lii(N)
var st = initRangeSet[int](0)
for i in range(N):
if i%2 == 0:
st.update(0,H[i],1)
else:
st.update(0,H[i],0)
echo now