Submission #48799502

---

Source Code Expand

class SegTree
  attr_accessor(:arr, :size)

  def initialize(n)
    @size = 1<<(n-1).bit_length
    @arr = Array.new(@size*2-1,10**18)
  end

  def update(i,x)
    i += @size - 1
    @arr[i] = x
    while i > 0
      i = (i-1)/2
      @arr[i] = op(@arr[i*2+1], @arr[i*2+2])
    end
  end

  def query(l,r) #[l,r)
    l += @size - 1
    r += @size - 1
    ret_l = 10**18
    ret_r = 10**18
    while l < r
      if l & 1 == 0
        ret_l = op(ret_l, @arr[l])
      end
      if r & 1 == 0
        ret_r = op(@arr[r-1],ret_r)
      end
      l = l/2
      r = (r-1)/2
    end
    return op(ret_l,ret_r)
  end

  def op(a,b) #ここを変える場合、@arrの初期値とquery()内のret_l,ret_rを変える必要があるから注意
    [a,b].min
  end

  def top()
    @arr[0]
  end
end

n,k = gets.split.map(&:to_i)
sx,sy = gets.split.map(&:to_i)
seg = SegTree.new(k+2)
0.upto(k-1) do |i|
  seg.update(i,10**18)
end
now = 0
add = 0
pre_x = 0
pre_y = 0
n.times do |i|
  x,y = gets.split.map(&:to_i)
  if i == 0
    seg.update(now,((x-sx)**2+(y-sy)**2)**0.5)
  else
    tohome = ((x-sx)**2+(y-sy)**2)**0.5
    tohome2 = ((pre_x-sx)**2+(pre_y-sy)**2)**0.5
    val = -((x-pre_x)**2+(y-pre_y)**2)**0.5 + tohome + tohome2
    min = seg.query(0,k)
    seg.update(now,min+val)
    add += ((x-pre_x)**2+(y-pre_y)**2)**0.5
  end
  now += 1
  now %= k
  pre_x = x
  pre_y = y
end
puts seg.query(0,k)+add+((pre_x-sx)**2+(pre_y-sy)**2)**0.5

Submission Info

Judge Result