Submission #19868017

---

Source Code Expand

n, k = gets.chomp.split(' ').map(&:to_i)
p    = gets.chomp.split(' ').map(&:to_i)

max = []
min = []
k.times do |i|
  until max.empty?
    break if max.first[0] > p[i]

    max.shift
  end
  until min.empty?
    break if min.first[0] < p[i]

    min.shift
  end
  max << [p[i], i]
  min << [p[i], i]
end

ans = n - k + 1
k.upto(n - 1) do |i|
  mi = [10 ** 18, 10 ** 18]
  max.shift if !max.empty? && i - max.first[1] >= k
  mi = min.shift if !min.empty? && i - min.first[1] >= k
  until max.empty?
    break if max.first[0] > p[i]

    max.shift
  end
  until min.empty?
    break if min.first[0] < p[i]

    min.shift
  end
  max << [p[i], i]
  min << [p[i], i]
  ans -= 1 if mi[1] == i - k && max.first[1] == i
end

puts ans

Submission Info

Judge Result