結果
問題 | No.2611 Count 01 |
ユーザー |
|
提出日時 | 2024-01-07 01:26:42 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 5,728 ms / 6,000 ms |
コード長 | 2,588 bytes |
コンパイル時間 | 3,396 ms |
コンパイル使用メモリ | 69,540 KB |
実行使用メモリ | 240,664 KB |
最終ジャッジ日時 | 2024-09-28 03:32:07 |
合計ジャッジ時間 | 114,027 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import strutils, sequtils, dequestype stdinReader = objectbuf: Deque[string]func newStdinReader(): stdinReader =result = stdinReader(buf: initDeque[string]())proc readString(sr: var stdinReader): string =if sr.buf.len == 0:sr.buf = stdin.readLine.split.toDequesr.buf.popFirstproc readInt(sr: var stdinReader): int =readString(sr).parseInttype SegmentTree[T] = objectn: intdata: seq[T]func init[T](n: int): SegmentTree[T] =var n2 = 1while n2 < n:n2 *= 2SegmentTree[T](n: n2, data: newSeq[T](n2 * 2))proc build[T](st: var SegmentTree[T], a: seq[T]) =for i, x in a:st.data[i + st.n] = xfor i in countdown(st.n - 1, 1):st.data[i] = st.data[i * 2] + st.data[i * 2 + 1]proc update[T](st: var SegmentTree[T], i: int, x: T) =var k = i + st.nst.data[k] = xwhile k > 1:k = k div 2st.data[k] = st.data[k * 2] + st.data[k * 2 + 1]func query[T](st: SegmentTree[T], l: int, r: int): T =varl = l + st.nr = r + st.nvar ls, rs: Twhile l < r:if (l and 1) == 1:ls = ls + st.data[l]l += 1if (r and 1) == 1:r -= 1rs = st.data[r] + rsl = l div 2r = r div 2ls + rsconst MOD = 998244353type Matrix = seq[seq[int]]func `+`(a, b: Matrix): Matrix =if a.len == 0:return bif b.len == 0:return aresult = newSeqWith(a.len, newSeq[int](b[0].len))for i in 0 ..< a.len:for j in 0 ..< b[0].len:for k in 0 ..< a[0].len:result[i][j] = (result[i][j] + a[i][k] * b[k][j]) mod MODlet node: array[2, Matrix] = [@[@[1, 0, 0, 0, 0, 0],@[1, 1, 0, 0, 0, 0],@[1, 1, 1, 0, 0, 0],@[0, 0, 0, 1, 0, 0],@[0, 0, 0, 1, 1, 0],@[0, 0, 0, 1, 1, 1],],@[@[1, 0, 0, 0, 0, 0],@[1, 1, 0, 0, 0, 0],@[0, 0, 1, 0, 0, 0],@[1, 1, 0, 1, 0, 0],@[0, 0, 1, 0, 1, 0],@[0, 0, 1, 0, 1, 1],]]var reader = newStdinReader()let (n, q) = (reader.readInt, reader.readInt)let s = reader.readStringvar sSeq = s.mapIt(int(it) - int('0'))var st = init[Matrix](n)st.build(sSeq.mapIt(node[it]))for _ in 0..<q:let t = reader.readIntif t == 1:let i = reader.readInt - 1sSeq[i] = 1 - sSeq[i]st.update(i, node[sSeq[i]])else:let (l, r) = (reader.readInt - 1, reader.readInt)let ans = st.query(l, r)echo ans[5][0]