結果

問題 No.318 学学学学学
ユーザー yuly3yuly3
提出日時 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]

ソースコード

diff # 

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()
0