CSAcademy #050 D. Min Races

csa050-d.rb

class SegmentTree
  attr_accessor :n, :dat
  def initialize(n)
    @n = n
    @dat = Array.new(4 * @n - 1, 0)
  end

  def update(k, a, node, l, r)
    if l == r
      @dat[node] = a
      return
    end

    mid = (l + r) / 2
    if k <= mid
      update(k, a, 2 * node, l, mid)
    else
      update(k, a, 2 * node + 1, mid + 1, r)
    end
    if @dat[2 * node] > @dat[2 * node + 1]
      @dat[node] = @dat[2 * node]
    else
      @dat[node] = @dat[2 * node + 1]
    end
  end
  def query(a, b, node, l, r)
    if (r < a) || (b < l)
      return 0
    end
    if (a <= l) && (r <= b)
      return @dat[node]
    end
    mid = (l + r) / 2
    vl = query(a, b, node * 2, l, mid)
    vr = query(a, b, node * 2 + 1, mid + 1, r)
    if vl > vr
      return vl
    else
      return vr
    end
  end
end

n, k = gets.chomp.split(" ").map(&:to_i)
drivers = Array.new(n)
n.times do
  a, b = gets.chomp.split(" ").map(&:to_i)
  drivers[b-1] = a
end

mx = 0
st = SegmentTree.new(n)

drivers.each do |cls|
  v = st.query(cls, n, 1, 1, n) + 1
  st.update(cls, v, 1, 1, n)
  mx = v if v > mx
end
puts mx