結果

問題 No.318 学学学学学
ユーザー LeonardoneLeonardone
提出日時 2015-12-11 23:25:01
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 2,112 bytes
コンパイル時間 42 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 33,024 KB
最終ジャッジ日時 2024-09-15 08:27:39
合計ジャッジ時間 6,697 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 149 ms
19,584 KB
testcase_01 AC 236 ms
15,948 KB
testcase_02 WA -
testcase_03 AC 203 ms
14,452 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#! ruby
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU

def gs(); gets.chomp; end
def gi(); gets.to_i; end
def gss(); gets.chomp.split; end
def gis(); gss.map(&:to_i); end

def bl(n); n < 2 ? 1 : 1 + bl(n >> 1); end

class ST
    def initialize(n)
        @N = n
        @L = (1 << bl(n).succ)
        @s = [nil] * @L
    end
    def put(x0, x1, v)
        t = [[x0, x1, 0, 1, @N]]
        while !t.empty? do
            z0, z1, i, y0, y1 = t.pop
            if y0 == z0 && y1 == z1
                @s[i] = v
                next
            end
            ym = (y0 + y1) >> 1
            j = i.succ << 1
            if z0 > ym
                if !@s[i].nil?
                    w = @s[i]
                    @s[i] = nil
                    put(y0, ym, w)
                    put(z1 + 1, y1, w) if y1 > z1
                end
                t << [z0, z1, j, ym + 1, y1]
            elsif z1 <= ym
                if !@s[i].nil?
                    w = @s[i]
                    @s[i] = nil
                    put(ym + 1, y1, w)
                    put(y0, z0 - 1, w) if y0 < z0
                end
                t << [z0, z1, j - 1, y0, ym]
            else
                if !@s[i].nil?
                    w = @s[i]
                    @s[i] = nil
                    put(y0, z0 - 1, w) if y0 < z0
                    put(z1 + 1, y1, w) if y1 > z1
                end
                t << [z0, ym, j - 1, y0, ym]
                t << [ym + 1, z1, j, ym + 1, y1]
            end
        end
    end
    def get(n)
        i, y0, y1 = 0, 1, @N
        while i < @L && @s[i].nil? do
            ym = (y0 + y1) >> 1
            i = i.succ << 1
            if n > ym
                y0 = ym + 1
            else
                y1 = ym
                i -= 1
            end
        end
        i < @L ? @s[i] : nil
    end
end


n = gi
a = gis

m = {}

(1..n).each do |i|
    k = a[i - 1]
    if m.key? k
        m[k] << i
    else
        m[k] = [i]
    end
end

st = ST.new(n)

m.keys.sort.each do |k|
    mn, mx = m[k].minmax
    st.put(mn, mx, k)
end

puts (1..n).map{|i| st.get(i)} * " "
0