結果

問題 No.318 学学学学学
ユーザー Leonardone
提出日時 2015-12-11 23:44:16
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,275 bytes
コンパイル時間 57 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 105,168 KB
最終ジャッジ日時 2024-09-15 08:29:04
合計ジャッジ時間 6,739 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
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?
                    @s[j] = @s[j - 1] = @s[i]
                    @s[i] = nil
                end
                t << [z0, z1, j, ym + 1, y1]
            elsif z1 <= ym
                if !@s[i].nil?
                    @s[j] = @s[j - 1] = @s[i]
                    @s[i] = nil
                end
                t << [z0, z1, j - 1, y0, ym]
            else
                if !@s[i].nil?
                    @s[j] = @s[j - 1] = @s[i]
                    @s[i] = nil
                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
    def gets()
        r = []
        t = [[0, 1, @N]]
        while !t.empty?
            i, y0, y1 = t.pop
            if @s[i].nil?
                j = i.succ << 1
                ym = (y0 + y1) >> 1
                t << [j, ym + 1, y1]
                t << [j - 1, y0, ym]
            else
                v = @s[i]
                r += [v] * (y1 - y0 + 1)
            end
        end
        r
    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 st.gets * " "
0