結果
問題 | No.1234 典型RMQ |
ユーザー | yuly3 |
提出日時 | 2020-09-21 13:57:41 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 4,980 bytes |
コンパイル時間 | 5,142 ms |
コンパイル使用メモリ | 72,584 KB |
実行使用メモリ | 23,072 KB |
最終ジャッジ日時 | 2023-08-08 19:04:18 |
合計ジャッジ時間 | 12,437 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,384 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 263 ms
19,628 KB |
testcase_07 | AC | 216 ms
8,112 KB |
testcase_08 | AC | 270 ms
21,104 KB |
testcase_09 | AC | 244 ms
13,100 KB |
testcase_10 | AC | 264 ms
21,520 KB |
testcase_11 | AC | 259 ms
19,508 KB |
testcase_12 | AC | 238 ms
12,900 KB |
testcase_13 | AC | 209 ms
7,876 KB |
testcase_14 | AC | 240 ms
12,712 KB |
testcase_15 | AC | 229 ms
11,956 KB |
testcase_16 | AC | 259 ms
20,948 KB |
testcase_17 | AC | 231 ms
12,448 KB |
testcase_18 | AC | 201 ms
7,660 KB |
testcase_19 | AC | 270 ms
21,544 KB |
testcase_20 | AC | 191 ms
21,828 KB |
testcase_21 | AC | 251 ms
19,580 KB |
testcase_22 | AC | 234 ms
22,288 KB |
testcase_23 | AC | 234 ms
22,664 KB |
testcase_24 | AC | 235 ms
22,400 KB |
testcase_25 | AC | 235 ms
22,752 KB |
testcase_26 | AC | 237 ms
23,072 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,384 KB |
testcase_29 | AC | 2 ms
4,380 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] = var 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] = var LV = bit_length(init_value.len - 1) N0 = 1 shl LV data = newSeqWith(2*N0, ide_ele) lazy_data = newSeqWith(2*N0, lazy_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 a, ans: seq[int] lazy_seg_tree: LazySegmentTree[int, int] proc solve() = let _ = input().parseInt a = input().split.map(parseInt) lazy_seg_tree = toLazySegmentTree(a, 10^18, 0, (a, b) => min(a, b), (a, b) => a + b, (a, b) => a + b) let Q = input().parseInt var ki, li, ri, ci: int for _ in 0..<Q: (ki, li, ri, ci) = input().split.map(parseInt) dec li if ki == 1: lazy_seg_tree.update(li, ri, ci) else: ans.add(lazy_seg_tree.query(li, ri)) echo ans.join("\n") when is_main_module: solve()