結果

問題 No.318 学学学学学
ユーザー Leonardone
提出日時 2015-12-11 23:25:01
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 2,112 bytes
コンパイル時間 42 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 33,024 KB
最終ジャッジ日時 2024-09-15 08:27:39
合計ジャッジ時間 6,697 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 3 WA * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
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