結果

問題 No.1137 Circles
ユーザー yuruhiyayuruhiya
提出日時 2021-02-04 18:48:54
言語 Crystal
(1.11.2)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 1,220 bytes
コンパイル時間 21,505 ms
コンパイル使用メモリ 253,656 KB
実行使用メモリ 8,672 KB
最終ジャッジ日時 2023-09-13 15:25:51
合計ジャッジ時間 22,405 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
7,624 KB
testcase_01 AC 34 ms
8,672 KB
testcase_02 AC 7 ms
7,824 KB
testcase_03 AC 20 ms
8,588 KB
testcase_04 AC 25 ms
8,544 KB
testcase_05 AC 10 ms
8,612 KB
testcase_06 AC 29 ms
8,592 KB
testcase_07 AC 18 ms
8,592 KB
testcase_08 AC 29 ms
8,540 KB
testcase_09 AC 14 ms
8,548 KB
testcase_10 AC 19 ms
8,468 KB
testcase_11 AC 21 ms
8,536 KB
testcase_12 AC 36 ms
8,528 KB
testcase_13 AC 14 ms
8,556 KB
testcase_14 AC 34 ms
8,532 KB
testcase_15 AC 16 ms
8,592 KB
testcase_16 AC 20 ms
8,488 KB
testcase_17 AC 8 ms
8,328 KB
testcase_18 AC 29 ms
8,484 KB
testcase_19 AC 15 ms
8,528 KB
testcase_20 AC 13 ms
8,608 KB
testcase_21 AC 7 ms
7,548 KB
権限があれば一括ダウンロードができます

ソースコード

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