結果

問題 No.1490 スライムと爆弾
ユーザー yuruhiyayuruhiya
提出日時 2021-04-24 19:48:08
言語 Crystal
(1.11.2)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 3,401 bytes
コンパイル時間 18,875 ms
コンパイル使用メモリ 258,888 KB
実行使用メモリ 114,828 KB
最終ジャッジ日時 2023-09-17 13:45:25
合計ジャッジ時間 23,679 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,712 KB
testcase_03 AC 3 ms
4,436 KB
testcase_04 AC 3 ms
4,620 KB
testcase_05 AC 3 ms
4,576 KB
testcase_06 AC 2 ms
4,472 KB
testcase_07 AC 2 ms
4,540 KB
testcase_08 AC 3 ms
4,788 KB
testcase_09 AC 3 ms
4,512 KB
testcase_10 AC 2 ms
4,420 KB
testcase_11 AC 2 ms
4,424 KB
testcase_12 AC 3 ms
4,608 KB
testcase_13 AC 130 ms
55,200 KB
testcase_14 AC 184 ms
86,908 KB
testcase_15 AC 101 ms
64,924 KB
testcase_16 AC 119 ms
50,840 KB
testcase_17 AC 91 ms
63,552 KB
testcase_18 AC 165 ms
78,028 KB
testcase_19 AC 149 ms
74,732 KB
testcase_20 AC 115 ms
70,400 KB
testcase_21 AC 83 ms
67,664 KB
testcase_22 AC 140 ms
59,584 KB
testcase_23 AC 2 ms
4,384 KB
testcase_24 AC 3 ms
4,520 KB
testcase_25 AC 222 ms
113,128 KB
testcase_26 AC 218 ms
113,324 KB
testcase_27 AC 228 ms
113,324 KB
testcase_28 AC 154 ms
102,996 KB
testcase_29 AC 160 ms
102,904 KB
testcase_30 AC 300 ms
114,828 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