結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | tomerun |
提出日時 | 2024-02-23 21:48:36 |
言語 | Crystal (1.11.2) |
結果 |
AC
|
実行時間 | 314 ms / 2,500 ms |
コード長 | 2,004 bytes |
コンパイル時間 | 12,348 ms |
コンパイル使用メモリ | 293,044 KB |
実行使用メモリ | 19,556 KB |
最終ジャッジ日時 | 2024-02-23 21:49:25 |
合計ジャッジ時間 | 22,462 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 1 ms
6,676 KB |
testcase_02 | AC | 113 ms
8,832 KB |
testcase_03 | AC | 24 ms
6,676 KB |
testcase_04 | AC | 151 ms
15,344 KB |
testcase_05 | AC | 126 ms
13,348 KB |
testcase_06 | AC | 61 ms
7,040 KB |
testcase_07 | AC | 119 ms
11,264 KB |
testcase_08 | AC | 53 ms
6,676 KB |
testcase_09 | AC | 292 ms
18,436 KB |
testcase_10 | AC | 294 ms
19,488 KB |
testcase_11 | AC | 295 ms
18,256 KB |
testcase_12 | AC | 291 ms
18,256 KB |
testcase_13 | AC | 314 ms
19,548 KB |
testcase_14 | AC | 292 ms
19,528 KB |
testcase_15 | AC | 290 ms
17,976 KB |
testcase_16 | AC | 272 ms
19,472 KB |
testcase_17 | AC | 272 ms
18,464 KB |
testcase_18 | AC | 283 ms
19,500 KB |
testcase_19 | AC | 268 ms
19,452 KB |
testcase_20 | AC | 270 ms
19,468 KB |
testcase_21 | AC | 270 ms
19,532 KB |
testcase_22 | AC | 292 ms
19,468 KB |
testcase_23 | AC | 255 ms
19,556 KB |
testcase_24 | AC | 259 ms
19,496 KB |
testcase_25 | AC | 259 ms
19,496 KB |
testcase_26 | AC | 257 ms
19,544 KB |
testcase_27 | AC | 264 ms
19,556 KB |
testcase_28 | AC | 257 ms
19,528 KB |
testcase_29 | AC | 260 ms
19,532 KB |
testcase_30 | AC | 252 ms
19,484 KB |
testcase_31 | AC | 297 ms
19,532 KB |
testcase_32 | AC | 205 ms
15,584 KB |
ソースコード
n, a = read_line.split.map(&.to_i) x = read_line.split.map(&.to_i) t = read_line.to_i lrs = Array.new(t) { read_line.split.map(&.to_i) } coords = x.dup.sort.uniq c2i = Hash(Int32, Int32).new coords.each.with_index do |c, i| c2i[c] = i end segtree = 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 !ri ri = coords.size - 1 else ri -= 1 end segtree.set(li, ri + 1, i + 1) end n.times do |i| ans = segtree.get(c2i[x[i]]) puts ans <= 0 ? -1 : ans end class RangeSetSegTree(T) @ar : Array(T) @size : Int32 @op : Proc(T, T, T) @zero : T def initialize(s : Int32, @op : Proc(T, T, T), @zero : T) @size = 1 while @size < s @size *= 2 end @ar = Array.new(@size * 2, @zero) end def initialize(init : Array(T), @op : Proc(T, T, T), @zero : T) @size = 1 while @size < init.size @size *= 2 end @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]) end end def get(pos : Int32) ret = @zero bit = 1 base = @size while base > 0 ret = @op.call(ret, @ar[base + (pos >> (bit - 1))]) bit += 1 base >>= 1 end return ret end def set(lo : Int32, hi : Int32, v : T) # [lo, hi) bit = @size.trailing_zeros_count len = @size base = 1 while len > 0 nlo = (lo + len - 1) & ~(len - 1) phi = hi & ~(len - 1) if nlo + len <= hi i = base + (nlo >> bit) @ar[i] = @op.call(v, @ar[i]) end if lo <= phi - len i = base + (phi >> bit) - 1 @ar[i] = @op.call(v, @ar[i]) end bit -= 1 len >>= 1 base <<= 1 end end end