結果
問題 | No.2611 Count 01 |
ユーザー |
|
提出日時 | 2024-01-07 01:43:43 |
言語 | Nim (2.2.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,705 bytes |
コンパイル時間 | 5,902 ms |
コンパイル使用メモリ | 67,068 KB |
実行使用メモリ | 196,732 KB |
最終ジャッジ日時 | 2024-09-28 03:28:10 |
合計ジャッジ時間 | 40,510 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | WA * 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, e: T): SegmentTree[T] =var n2 = 1while n2 < n:n2 *= 2SegmentTree[T](n: n2, data: newSeqWith[T](n2 * 2, e))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 = array[6, array[6, int]]func `+`(a, b: Matrix): Matrix =if a.len == 0:return bif b.len == 0:return afor i in 0 ..< a.len:for j in 0..i:for k in 0..i: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],]]let identity: Matrix = [[1, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 0],[0, 0, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 1, 0],[0, 0, 0, 0, 0, 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, identity)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]