結果
問題 |
No.1471 Sort Queries
|
ユーザー |
![]() |
提出日時 | 2021-04-09 21:42:21 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 13,569 ms |
コンパイル使用メモリ | 296,864 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 04:46:44 |
合計ジャッジ時間 | 15,034 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
lib C fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64 end class String def to_i64 C.strtoll(self, nil, 10) end end # require "utility/CulSum" # description : 累積和 class CulSum(T) def initialize(a : Array(T)) @n = a.size @s = Array(T).new(@n + 1, T.zero) @n.times do |i| @s[i + 1] = @s[i] + a[i] end end def initialize(@n : Int32, &f : Int32 -> T) @s = Array(T).new(@n + 1, T.zero) @n.times do |i| @s[i + 1] = @s[i] + yield(i) end end def initialize(a, &f) @n = a.size @s = Array(T).new(@n + 1, T.zero) @n.times do |i| @s[i + 1] = @s[i] + yield(a[i]) end end def [](left : Int32, count : Int32) @s[left + count] - @s[left] end def [](range : Range) self[*Indexable.range_to_index_and_count(range, @n) || raise IndexError.new] end def to_a (0...@n).map { |i| self[i..i] } end end n, q = read_line.split.map(&.to_i) s = read_line sum = ('a'..'z').map { |c| CulSum(Int32).new(s) { |c2| c == c2 ? 1 : 0 } } q.times do l, r, x = read_line.split.map(&.to_i) l -= 1 cnt = (0...26).map { |i| sum[i][l...r] } cnt_sum = 0 puts 'a' + cnt.each_with_index.find { |c, i| cnt_sum += c cnt_sum >= x }.not_nil![1] end