結果

問題 No.318 学学学学学
ユーザー LeonardoneLeonardone
提出日時 2015-12-11 23:44:16
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 2,275 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 11,440 KB
実行使用メモリ 116,656 KB
最終ジャッジ日時 2023-10-13 11:29:47
合計ジャッジ時間 7,020 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 259 ms
112,772 KB
testcase_01 AC 455 ms
116,556 KB
testcase_02 AC 553 ms
116,656 KB
testcase_03 AC 379 ms
114,396 KB
testcase_04 AC 509 ms
114,568 KB
testcase_05 TLE -
testcase_06 -- -
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?
                    @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