結果
問題 | No.945 YKC饅頭 |
ユーザー | yuly3 |
提出日時 | 2020-09-22 09:30:38 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 904 ms / 2,000 ms |
コード長 | 5,121 bytes |
コンパイル時間 | 4,173 ms |
コンパイル使用メモリ | 73,628 KB |
実行使用メモリ | 21,228 KB |
最終ジャッジ日時 | 2023-09-08 02:50:02 |
合計ジャッジ時間 | 23,784 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 5 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 3 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,388 KB |
testcase_07 | AC | 3 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,384 KB |
testcase_10 | AC | 3 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | AC | 3 ms
4,380 KB |
testcase_13 | AC | 4 ms
4,376 KB |
testcase_14 | AC | 4 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,380 KB |
testcase_17 | AC | 4 ms
4,384 KB |
testcase_18 | AC | 3 ms
4,384 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 3 ms
4,380 KB |
testcase_22 | AC | 4 ms
4,376 KB |
testcase_23 | AC | 4 ms
4,380 KB |
testcase_24 | AC | 5 ms
4,376 KB |
testcase_25 | AC | 5 ms
4,380 KB |
testcase_26 | AC | 4 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,376 KB |
testcase_29 | AC | 2 ms
4,384 KB |
testcase_30 | AC | 2 ms
4,380 KB |
testcase_31 | AC | 36 ms
7,492 KB |
testcase_32 | AC | 15 ms
12,232 KB |
testcase_33 | AC | 172 ms
20,684 KB |
testcase_34 | AC | 443 ms
12,040 KB |
testcase_35 | AC | 740 ms
20,940 KB |
testcase_36 | AC | 539 ms
4,380 KB |
testcase_37 | AC | 500 ms
5,296 KB |
testcase_38 | AC | 459 ms
7,584 KB |
testcase_39 | AC | 99 ms
12,036 KB |
testcase_40 | AC | 85 ms
20,808 KB |
testcase_41 | AC | 31 ms
12,032 KB |
testcase_42 | AC | 661 ms
12,000 KB |
testcase_43 | AC | 463 ms
4,380 KB |
testcase_44 | AC | 569 ms
20,672 KB |
testcase_45 | AC | 750 ms
11,964 KB |
testcase_46 | AC | 14 ms
11,860 KB |
testcase_47 | AC | 433 ms
12,144 KB |
testcase_48 | AC | 90 ms
4,388 KB |
testcase_49 | AC | 177 ms
12,196 KB |
testcase_50 | AC | 776 ms
12,004 KB |
testcase_51 | AC | 894 ms
21,228 KB |
testcase_52 | AC | 888 ms
21,084 KB |
testcase_53 | AC | 900 ms
21,084 KB |
testcase_54 | AC | 904 ms
21,088 KB |
testcase_55 | AC | 902 ms
21,024 KB |
testcase_56 | AC | 13 ms
20,936 KB |
testcase_57 | AC | 14 ms
20,960 KB |
testcase_58 | AC | 373 ms
21,064 KB |
testcase_59 | AC | 463 ms
21,136 KB |
testcase_60 | AC | 168 ms
21,100 KB |
testcase_61 | AC | 404 ms
21,160 KB |
testcase_62 | AC | 382 ms
21,056 KB |
testcase_63 | AC | 18 ms
21,088 KB |
testcase_64 | AC | 182 ms
21,068 KB |
testcase_65 | AC | 146 ms
20,996 KB |
testcase_66 | AC | 137 ms
21,176 KB |
testcase_67 | AC | 281 ms
21,164 KB |
testcase_68 | AC | 172 ms
21,064 KB |
testcase_69 | AC | 60 ms
20,996 KB |
testcase_70 | AC | 75 ms
21,020 KB |
testcase_71 | AC | 76 ms
21,172 KB |
testcase_72 | AC | 224 ms
21,212 KB |
testcase_73 | AC | 433 ms
21,012 KB |
ソースコード
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[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 eval(a, b: int): int = if b == -1: return a return b lazy_seg_tree = toLazySegmentTree(newSeqWith(N, 1), 0, -1, (a, b) => a + b, eval, (a, b) => b) var li, ri: int ti: string ans = [0, 0, 0] for _ in 0..<M: let query = input().split li = query[0].parseInt - 1 ri = query[1].parseInt ti = query[2] ans[ykc_num[ti]] += lazy_seg_tree.query(li, ri) lazy_seg_tree.update(li, ri, 0) echo ans.join(" ") when is_main_module: solve()