結果

問題 No.1490 スライムと爆弾
ユーザー yuruhiyayuruhiya
提出日時 2021-04-24 19:48:08
言語 Crystal
(1.11.2)
結果
AC  
実行時間 335 ms / 2,000 ms
コード長 3,401 bytes
コンパイル時間 15,448 ms
コンパイル使用メモリ 293,960 KB
実行使用メモリ 111,360 KB
最終ジャッジ日時 2024-07-04 09:12:34
合計ジャッジ時間 18,994 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 135 ms
52,864 KB
testcase_14 AC 186 ms
84,096 KB
testcase_15 AC 114 ms
63,412 KB
testcase_16 AC 124 ms
49,664 KB
testcase_17 AC 107 ms
61,564 KB
testcase_18 AC 185 ms
74,880 KB
testcase_19 AC 169 ms
73,472 KB
testcase_20 AC 134 ms
68,608 KB
testcase_21 AC 102 ms
65,536 KB
testcase_22 AC 142 ms
58,112 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 249 ms
110,592 KB
testcase_26 AC 242 ms
110,532 KB
testcase_27 AC 243 ms
110,588 KB
testcase_28 AC 164 ms
101,376 KB
testcase_29 AC 168 ms
101,332 KB
testcase_30 AC 335 ms
111,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "utility/Imos2D"
class Imos2D(T)
  @builded = false

  getter height : Int32
  getter width : Int32

  def initialize(@height, @width)
    @table = Array(Array(T)).new(@height + 1) {
      Array(T).new(@width + 1, T.zero)
    }
  end

  def initialize(@height, @width, init_val : T)
    @table = Array(Array(T)).new(@height + 1) {
      Array(T).new(@width + 1, T.zero)
    }
  end

  def add(ys : Int32, yc : Int32, xs : Int32, xc : Int32, val : T)
    raise "self had been called `build`" if @builded
    raise ArgumentError.new "Negative count: #{yc}" if yc < 0
    raise ArgumentError.new "Negative count: #{xc}" if xc < 0
    @table[ys + yc][xs + xc] += val
    @table[ys + yc][xs] -= val
    @table[ys][xs + xc] -= val
    @table[ys][xs] += val
  end

  def add(y : Range, x : Range, val : T)
    ys, yc = Indexable.range_to_index_and_count(y, height) || raise IndexError.new
    xs, xc = Indexable.range_to_index_and_count(x, width) || raise IndexError.new
    add(ys, yc, xs, xc, val)
  end

  def build : Array(Array(T))
    raise "self had been called `build`" if @builded
    @builded = true
    (0..height).each do |y|
      (1..width).each do |x|
        @table[y][x] += @table[y][x - 1]
      end
    end
    (1..height).each do |y|
      (0..width).each do |x|
        @table[y][x] += @table[y - 1][x]
      end
    end
    (0...height).map { |i| @table[i][0...width] }
  end

  def [](y : Int32, x : Int32) : T
    raise IndexError.new unless 0 <= y < height
    raise IndexError.new unless 0 <= x < width
    @table[y][x]
  end
end
# require "utility/CulSum2D"
class CulSum2D(T)
  getter height : Int32
  getter width : Int32

  def initialize(a : Array(Array(T)))
    @height = a.size
    raise ArgumentError.new unless height > 0
    @width = a[0].size
    raise ArgumentError.new unless a.map(&.size).all?(width)

    @s = Array(Array(T)).new(height + 1) { Array.new(width + 1, T.zero) }
    (0...height).each do |i|
      (0...width).each do |j|
        @s[i + 1][j + 1] = @s[i][j + 1] + @s[i + 1][j] - @s[i][j] + a[i][j]
      end
    end
  end

  def initialize(@height : Int32, @width : Int32, &f : Int32, Int32 -> T)
    raise ArgumentError.new unless height > 0
    raise ArgumentError.new unless width > 0
    @s = Array(Array(T)).new(height + 1) { Array.new(width + 1, T.zero) }
    (0...height).each do |i|
      (0...width).each do |j|
        @s[i + 1][j + 1] = @s[i][j + 1] + @s[i + 1][j] - @s[i][j] + yield(i, j)
      end
    end
  end

  def [](y_start, y_count, x_start, x_count)
    @s[y_start + y_count][x_start + x_count] - @s[y_start + y_count][x_start] -
      @s[y_start][x_start + x_count] + @s[y_start][x_start]
  end

  def [](y_range : Range, x_range : Range)
    ys, yc = Indexable.range_to_index_and_count(y_range, height) || raise IndexError.new
    xs, xc = Indexable.range_to_index_and_count(x_range, width) || raise IndexError.new
    self[ys, yc, xs, xc]
  end

  def to_a
    (0...@n).map { |i| self[i..i] }
  end
end
h, w, n, m = read_line.split.map(&.to_i)
tulra = (1..n).map { read_line.split.map(&.to_i) }
imos = Imos2D(Int64).new(h, w)
m.times do
  x, y, b, c = read_line.split.map(&.to_i)
  x_range = {x - 1 - b, 0}.max...{x + b, h}.min
  y_range = {y - 1 - b, 0}.max...{y + b, w}.min
  imos.add(x_range, y_range, c.to_i64)
end
sum = CulSum2D.new(imos.build)

puts tulra.count { |(t, u, l, r, a)|
  sum[t - 1...u, l - 1...r] < a
}
0