結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
![]() |
提出日時 | 2024-02-23 21:48:36 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,500 ms |
コード長 | 2,004 bytes |
コンパイル時間 | 12,252 ms |
コンパイル使用メモリ | 300,940 KB |
実行使用メモリ | 20,332 KB |
最終ジャッジ日時 | 2024-09-29 06:11:02 |
合計ジャッジ時間 | 21,687 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
n, a = read_line.split.map(&.to_i)x = read_line.split.map(&.to_i)t = read_line.to_ilrs = Array.new(t) { read_line.split.map(&.to_i) }coords = x.dup.sort.uniqc2i = Hash(Int32, Int32).newcoords.each.with_index do |c, i|c2i[c] = iendsegtree = RangeSetSegTree(Int32).new(Array.new(coords.size, -1), ->(x : Int32, y : Int32) { {x, y}.max }, 0)lrs.each.with_index do |lr, i|next if coords[-1] < lr[0]next if coords[0] > lr[1]li = coords.bsearch_index { |v, _| lr[0] <= v }.not_nil!ri = coords.bsearch_index { |v, _| lr[1] < v }if !riri = coords.size - 1elseri -= 1endsegtree.set(li, ri + 1, i + 1)endn.times do |i|ans = segtree.get(c2i[x[i]])puts ans <= 0 ? -1 : ansendclass RangeSetSegTree(T)@ar : Array(T)@size : Int32@op : Proc(T, T, T)@zero : Tdef initialize(s : Int32, @op : Proc(T, T, T), @zero : T)@size = 1while @size < s@size *= 2end@ar = Array.new(@size * 2, @zero)enddef initialize(init : Array(T), @op : Proc(T, T, T), @zero : T)@size = 1while @size < init.size@size *= 2end@ar = Array.new(@size, @zero)@ar.concat(init)@ar.concat([@zero] * (@size - init.size))(@size - 1).downto(1) do |i|@ar[i] = @op.call(@ar[i * 2], @ar[i * 2 + 1])endenddef get(pos : Int32)ret = @zerobit = 1base = @sizewhile base > 0ret = @op.call(ret, @ar[base + (pos >> (bit - 1))])bit += 1base >>= 1endreturn retenddef set(lo : Int32, hi : Int32, v : T)# [lo, hi)bit = @size.trailing_zeros_countlen = @sizebase = 1while len > 0nlo = (lo + len - 1) & ~(len - 1)phi = hi & ~(len - 1)if nlo + len <= hii = base + (nlo >> bit)@ar[i] = @op.call(v, @ar[i])endif lo <= phi - leni = base + (phi >> bit) - 1@ar[i] = @op.call(v, @ar[i])endbit -= 1len >>= 1base <<= 1endendend