test/datastructure/imos_test.cr

View this file on GitHub
Last update: 2021-10-17 17:15:41+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2013

Depends on

src/datastructure/imos.cr

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2013
require "../../src/datastructure/imos"
loop do
  n = read_line.to_i
  break if n == 0
  imos = Imos(Int32).new(24 * 60 * 60)
  n.times do
    s, t = read_line.split.map { |i|
      h, m, s = i.split(':').map(&.to_i)
      h * 3600 + m * 60 + s
    }
    imos.add(s...t, 1)
  end
  puts imos.build.max
end

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2013
# require "../../src/datastructure/imos"
class Imos(T)
  getter size : Int32
  @built = false

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

  def add(start : Int, count : Int, val : T) : Nil
    raise "self had been called `#build`" if @built
    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
  end

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

  def build : Array(T)
    raise "self had been called `#build`" if @built
    @built = true
    (0...size).map do |i|
      @a[i].tap { |x| @a[i + 1] += x }
    end
  end
end

loop do
  n = read_line.to_i
  break if n == 0
  imos = Imos(Int32).new(24 * 60 * 60)
  n.times do
    s, t = read_line.split.map { |i|
      h, m, s = i.split(':').map(&.to_i)
      h * 3600 + m * 60 + s
    }
    imos.add(s...t, 1)
  end
  puts imos.build.max
end