結果
| 問題 | No.3094 Stapler |
| ユーザー |
 kemuniku
|
| 提出日時 | 2025-04-06 18:19:49 |
| 言語 | Nim (2.2.0) |
| 結果 |
AC
|
| 実行時間 | 210 ms / 2,000 ms |
| コード長 | 13,037 bytes |
| コンパイル時間 | 4,043 ms |
| コンパイル使用メモリ | 78,936 KB |
| 実行使用メモリ | 68,396 KB |
| 最終ジャッジ日時 | 2025-06-20 02:32:18 |
| 合計ジャッジ時間 | 15,527 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 72 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: src/cplib/tmpl/sheep.nim
ImportExpand "cplib/tmpl/sheep" <=== "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 proc chmin[T](x: var T, y: T):bool=\n if x > y:\n x = y\n return true\n return false\n proc chmax[T](x: var T, y: T):bool=\n if x < y:\n x = y\n return true\n return false\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 when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 1001000027.int32\n const INF64*: int = int(3300300300300300491)\n \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"
# source: src/atcoder/lazysegtree.nim
ImportExpand "atcoder/lazysegtree" <=== "when not declared ATCODER_LAZYSEGTREE_HPP:\n const ATCODER_LAZYSEGTREE_HPP* = 1\n \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 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 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"
proc initRangeAddRangeMinSegtree[T](v:seq[T]):auto=
type S = (T,int)
type F = T
proc op(a,b:S):S=
if a[0] == b[0]:
return (a[0],a[1]+b[1])
elif a[0] < b[0]:
return a
else:
return b
proc e():S=(INF,1)
proc mapping(f:F,x:S):S=(x[0]+f,x[1])
proc composition(f,g:F):F=f+g
proc id():F=0
return LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v.mapit((it,1)))
var N = ii()
var Q = ii()
var st = initRangeAddRangeMinSegtree(newseqwith(N-1,0))
var querys: seq[(int,int)]
for i in range(Q):
var T = ii()
if T == 1:
var L,R = ii()-1
querys.add((L,R))
st.apply(L..<R,1)
elif T == 2:
var q = ii()-1
querys.add((-1,-1))
var (L,R) = querys[q]
st.apply(L..<R,-1)
else:
querys.add((-1,-1))
var (a,b) = st.all_prod()
if a == 0:
echo b+1
else:
echo 1