結果
問題 | No.318 学学学学学 |
ユーザー | yuly3 |
提出日時 | 2020-09-06 21:45:21 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 3,245 bytes |
コンパイル時間 | 6,930 ms |
コンパイル使用メモリ | 72,936 KB |
実行使用メモリ | 29,112 KB |
最終ジャッジ日時 | 2023-08-19 14:23:00 |
合計ジャッジ時間 | 10,872 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
5,272 KB |
testcase_01 | AC | 32 ms
8,280 KB |
testcase_02 | AC | 39 ms
8,320 KB |
testcase_03 | AC | 26 ms
7,320 KB |
testcase_04 | AC | 35 ms
8,048 KB |
testcase_05 | AC | 198 ms
29,112 KB |
testcase_06 | AC | 175 ms
24,296 KB |
testcase_07 | AC | 151 ms
21,304 KB |
testcase_08 | AC | 128 ms
20,984 KB |
testcase_09 | AC | 116 ms
19,868 KB |
testcase_10 | AC | 101 ms
19,864 KB |
testcase_11 | AC | 196 ms
28,952 KB |
testcase_12 | AC | 155 ms
24,088 KB |
testcase_13 | AC | 133 ms
21,068 KB |
testcase_14 | AC | 121 ms
20,980 KB |
testcase_15 | AC | 109 ms
19,960 KB |
testcase_16 | AC | 105 ms
20,084 KB |
testcase_17 | AC | 153 ms
25,952 KB |
testcase_18 | AC | 146 ms
26,164 KB |
testcase_19 | AC | 154 ms
25,996 KB |
testcase_20 | AC | 94 ms
20,124 KB |
testcase_21 | AC | 2 ms
4,384 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 1 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 2 ms
4,380 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 38) Warning: imported and not used: 'math' [UnusedImport] /home/judge/data/code/Main.nim(1, 70) Warning: imported and not used: 'sugar' [UnusedImport]
ソースコード
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 bit_length(n: Natural): Natural = if n == 0: return 0 let s = toBin(n, 60) return 60 - s.find('1') type DuelSegmentTree*[T] = ref object LV: Natural N0: Positive lazy_ide_ele: T lazy_data: seq[T] proc initDuelSegmentTree*[T](size: Positive, lazy_ide_ele: T): DuelSegmentTree[T] = var LV = bit_length(size - 1) N0 = 1 shl LV return DuelSegmentTree[T](LV: LV, N0: N0, lazy_ide_ele: lazy_ide_ele, lazy_data: newSeqWith(2 * N0, lazy_ide_ele)) iterator gindex*[T](self: var DuelSegmentTree[T], 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](self: var DuelSegmentTree[T], ids: seq[Natural]) = var idx: Natural v: T for id in reversed(ids): idx = id - 1 v = self.lazy_data[idx] if v == self.lazy_ide_ele: continue self.lazy_data[2*idx + 1] = v self.lazy_data[2*idx + 2] = v self.lazy_data[idx] = self.lazy_ide_ele proc update*[T](self: var DuelSegmentTree[T], left, right: Natural, x: T) = self.propagates(toSeq(self.gindex(left, right))) var L = left + self.N0 R = right + self.N0 while L < R: if (L and 1) == 1: self.lazy_data[L - 1] = x inc L if (R and 1) == 1: dec R self.lazy_data[R - 1] = x L = L shr 1 R = R shr 1 proc query*[T](self: var DuelSegmentTree[T], k: Natural): T = self.propagates(toSeq(self.gindex(k, k + 1))) return self.lazy_data[k + self.N0 - 1] var a, sorted_a, a_left, a_right, ans: seq[int] a_set: HashSet[int] compress: Table[int, int] duel_seg_tree: DuelSegmentTree[int] proc solve() = let n = input().parseInt a = input().split.map(parseInt) a_set = toHashSet(a) sorted_a = sorted(toSeq(a_set.items)) compress = initTable[int, int]() for idx, val in sorted_a: compress[val] = idx (a_left, a_right) = (newSeqWith(compress.len, -1), newSeqWith(compress.len, -1)) for i, ai in a: if a_left[compress[ai]] == -1: a_left[compress[ai]] = i else: a_right[compress[ai]] = i duel_seg_tree = initDuelSegmentTree(n, 0) for i, ai in sorted_a: if a_right[i] != -1: duel_seg_tree.update(a_left[i], a_right[i] + 1, ai) else: duel_seg_tree.update(a_left[i], a_left[i] + 1, ai) ans = newSeq[int](n) for i in 0..<n: ans[i] = duel_seg_tree.query(i) echo ans.join(" ") when is_main_module: solve()