結果
問題 | No.945 YKC饅頭 |
ユーザー | yuly3 |
提出日時 | 2020-09-22 08:58:26 |
言語 | Nim (2.0.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,330 bytes |
コンパイル時間 | 5,351 ms |
コンパイル使用メモリ | 73,700 KB |
実行使用メモリ | 50,772 KB |
最終ジャッジ日時 | 2023-09-08 02:14:46 |
合計ジャッジ時間 | 26,059 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,376 KB |
testcase_30 | AC | 1 ms
4,376 KB |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | AC | 26 ms
50,204 KB |
testcase_57 | AC | 26 ms
50,320 KB |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | WA | - |
testcase_71 | WA | - |
testcase_72 | WA | - |
testcase_73 | WA | - |
ソースコード
import algorithm, deques, heapqueue, math, sets, sequtils, strutils, sugar, tables proc input*(): string = return stdin.readLine proc chmax*[T: SomeNumber](num0: var T, num1: T) = num0 = max(num0, num1) proc chmin*[T: SomeNumber](num0: var T, num1: T) = num0 = min(num0, num1) proc `%=`*[T: SomeInteger](num0: var T, num1: T) = num0 = num0 mod num1 proc bit_length(n: Natural): Natural = const BIT_SIZE = 24 if n == 0: return 0 let s = toBin(n, BIT_SIZE) return BIT_SIZE - s.find('1') type LazySegmentTree*[T, K] = ref object LV: Natural N0: Positive ide_ele: T lazy_ide_ele: K data: seq[T] lazy_data: seq[K] fold: proc (a, b: T): T eval: proc (a: T, b: K): T merge: proc (a, b: K): K proc initLazySegmentTree*[T, K](size: Positive, ide_ele: T, lazy_ide_ele: K, fold: proc (a, b: T): T, eval: proc (a: T, b: K): T, merge: proc (a, b: K): K): LazySegmentTree[T, K] = let LV = bit_length(size - 1) N0 = 1 shl LV data = newSeqWith(2*N0, ide_ele) lazy_data = newSeqWith(2*N0, lazy_ide_ele) return LazySegmentTree[T, K](LV: LV, N0: N0, ide_ele: ide_ele, lazy_ide_ele: lazy_ide_ele, data: data, lazy_data: lazy_data, fold: fold, eval: eval, merge: merge) proc toLazySegmentTree*[T, K](init_value: openArray[T], ide_ele: T, lazy_ide_ele: K, fold: proc (a, b: T): T, eval: proc (a: T, b: K): T, merge: proc (a, b: K): K): LazySegmentTree[T, K] = let LV = bit_length(init_value.len - 1) N0 = 1 shl LV lazy_data = newSeqWith(2*N0, lazy_ide_ele) var data = newSeqWith(2*N0, ide_ele) for i, x in init_value: data[i + N0 - 1] = x for i in countdown(N0 - 2, 0): data[i] = fold(data[2*i + 1], data[2*i + 2]) return LazySegmentTree[T, K](LV: LV, N0: N0, ide_ele: ide_ele, lazy_ide_ele: lazy_ide_ele, data: data, lazy_data: lazy_data, fold: fold, eval: eval, merge: merge) iterator gindex*[T, K](self: var LazySegmentTree[T, K], left, right: Natural): Natural = var L = (left + self.N0) shr 1 R = (right + self.N0) shr 1 lc = if (left and 1) == 1: 0 else: bit_length(L and -L) rc = if (right and 1) == 1: 0 else: bit_length(R and -R) for i in 0..<self.LV: if rc <= i: yield R if L < R and lc <= i: yield L L = L shr 1 R = R shr 1 proc propagates*[T, K](self: var LazySegmentTree[T, K], ids: seq[Natural]) = var idx: Natural v: K for id in reversed(ids): idx = id - 1 v = self.lazy_data[idx] if v == self.lazy_ide_ele: continue # v = v shr 1 self.data[2*idx + 1] = self.eval(self.data[2*idx + 1], v) self.data[2*idx + 2] = self.eval(self.data[2*idx + 2], v) self.lazy_data[2*idx + 1] = self.merge(self.lazy_data[2*idx + 1], v) self.lazy_data[2*idx + 2] = self.merge(self.lazy_data[2*idx + 2], v) self.lazy_data[idx] = self.lazy_ide_ele proc update*[T, K](self: var LazySegmentTree[T, K], left, right: Natural, x: K) = let ids = toSeq(self.gindex(left, right)) self.propagates(ids) var L = left + self.N0 R = right + self.N0 # x = x while L < R: if (L and 1) == 1: self.lazy_data[L - 1] = self.merge(self.lazy_data[L - 1], x) self.data[L - 1] = self.eval(self.data[L - 1], x) inc L if (R and 1) == 1: dec R self.lazy_data[R - 1] = self.merge(self.lazy_data[R - 1], x) self.data[R - 1] = self.eval(self.data[R - 1], x) L = L shr 1 R = R shr 1 # x = x shl 1 var idx: Natural for id in ids: idx = id - 1 self.data[idx] = self.eval(self.fold(self.data[2*idx + 1], self.data[2*idx + 2]), self.lazy_data[idx]) proc query*[T, K](self: var LazySegmentTree[T, K], left, right: Natural): T = self.propagates(toSeq(self.gindex(left, right))) var L = left + self.N0 R = right + self.N0 res = self.ide_ele while L < R: if (L and 1) == 1: res = self.fold(res, self.data[L - 1]) inc L if (R and 1) == 1: dec R res = self.fold(res, self.data[R - 1]) L = L shr 1 R = R shr 1 return res var lazy_seg_tree: LazySegmentTree[array[4, int], int] proc solve() = var N, M: int (N, M) = input().split.map(parseInt) let ykc_num = {"Y": 0, "K": 1, "C": 2}.toTable proc fold(a, b: array[4, int]): array[4, int] = return [a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3]] proc eval(a: array[4, int], b: int): array[4, int] = if b == -1: return a var res = a res[b] += a[3] res[3] = 0 return res lazy_seg_tree = toLazySegmentTree(newSeqWith(N, [0, 0, 0, 1]), [0, 0, 0, 0], -1, fold, eval, (a, b) => b) var li, ri: int ti: string for _ in 0..<M: let query = input().split li = query[0].parseInt - 1 ri = query[1].parseInt ti = query[2] lazy_seg_tree.update(li, ri, ykc_num[ti]) let ans = lazy_seg_tree.query(0, N)[0..2] echo ans.join(" ") when is_main_module: solve()