結果

問題 No.1490 スライムと爆弾
ユーザー yuruhiya
提出日時 2021-04-24 19:48:08
言語 Crystal
(1.14.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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