結果

問題 No.1137 Circles
ユーザー yuruhiya
提出日時 2021-02-04 18:48:54
言語 Crystal
(1.14.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 1,220 bytes
コンパイル時間 13,843 ms
コンパイル使用メモリ 295,080 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 00:01:22
合計ジャッジ時間 14,575 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

lib C
  fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64
end

class String
  def to_i64
    C.strtoll(self, nil, 10)
  end
end

class Imos(T)
  @flag = false

  def initialize(@size : Int32)
    @a = Array(T).new(@size + 1, T.zero)
  end

  def initialize(@size : Int32, init_val : T)
    @a = Array(T).new(@size + 1, init_val)
  end

  getter size : Int32

  def add(start : Int, count : Int, val : T)
    raise "self had been called `build`" if @flag
    raise ArgumentError.new "Negative count: #{count}" if count < 0
    start += size if start < 0
    if 0 <= start <= size
      count = Math.min(count, size - start)
      @a[start] += val
      @a[start + count] -= val
    end
    nil
  end

  def add(range : Range, val : T)
    start, count = Indexable.range_to_index_and_count(range, size) || raise IndexError.new
    add(start, count, val)
  end

  def build
    raise "self had been called `build`" if @flag
    @flag = true
    (1..size).each do |i|
      @a[i] += @a[i - 1]
    end
    @a[0, size]
  end
end

n = read_line.to_i
MAX_X = 2 * 10 ** 5 + 5
imos = Imos(Int32).new(MAX_X * 2)
n.times do
  x, r = read_line.split.map &.to_i
  x += MAX_X
  imos.add(x - r...x + r, 1)
end
puts imos.build.max
0