結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
![]() |
提出日時 | 2024-02-23 21:48:36 |
言語 | Crystal (1.11.2) |
結果 |
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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 111 ms
8,064 KB |
testcase_03 | AC | 23 ms
6,820 KB |
testcase_04 | AC | 147 ms
15,288 KB |
testcase_05 | AC | 121 ms
11,648 KB |
testcase_06 | AC | 59 ms
7,040 KB |
testcase_07 | AC | 114 ms
12,176 KB |
testcase_08 | AC | 52 ms
6,816 KB |
testcase_09 | AC | 290 ms
18,312 KB |
testcase_10 | AC | 291 ms
20,332 KB |
testcase_11 | AC | 291 ms
18,756 KB |
testcase_12 | AC | 292 ms
19,316 KB |
testcase_13 | AC | 285 ms
18,684 KB |
testcase_14 | AC | 288 ms
18,404 KB |
testcase_15 | AC | 294 ms
18,368 KB |
testcase_16 | AC | 275 ms
19,432 KB |
testcase_17 | AC | 266 ms
18,076 KB |
testcase_18 | AC | 271 ms
19,564 KB |
testcase_19 | AC | 272 ms
19,424 KB |
testcase_20 | AC | 271 ms
18,376 KB |
testcase_21 | AC | 272 ms
18,812 KB |
testcase_22 | AC | 272 ms
18,352 KB |
testcase_23 | AC | 261 ms
19,924 KB |
testcase_24 | AC | 243 ms
19,640 KB |
testcase_25 | AC | 252 ms
19,628 KB |
testcase_26 | AC | 257 ms
18,440 KB |
testcase_27 | AC | 257 ms
18,540 KB |
testcase_28 | AC | 257 ms
20,120 KB |
testcase_29 | AC | 256 ms
19,384 KB |
testcase_30 | AC | 249 ms
19,544 KB |
testcase_31 | AC | 262 ms
19,340 KB |
testcase_32 | AC | 201 ms
13,440 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