Alitaulukot

INF = Integer(1e9)
class SegmentTree
  def initialize(v)
    @z = 1 << v.size.bit_length
    @pmi = Array.new(@z * 2, INF)
    @pma = Array.new(@z * 2, 0)
    v.each_with_index do |x, i|
      @pmi[i + @z] = @pma[i + @z] = x
    end
    (@z - 1).downto(1) do |i|
      @pma[i] = [@pma[i * 2], @pma[i * 2 + 1]].max
      @pmi[i] = [@pmi[i * 2], @pmi[i * 2 + 1]].min
    end
  end

  def get(a, b)
    a += @z
    b += @z
    rma = 0
    rmi = INF
    while a <= b
      if a.odd?
        rma = [rma, @pma[a]].max
        rmi = [rmi, @pmi[a]].min
        a += 1
      end
      if b.even?
        rma = [rma, @pma[b]].max
        rmi = [rmi, @pmi[b]].min
        b -= 1
      end
      a /= 2
      b /= 2
    end
    rma - rmi
  end
end
n, k = gets.split.map(&:to_i)
v = gets.split.map(&:to_i)
tree = SegmentTree.new(v)
r = 0
j = 0
(0..n - 1).each do |i|
  j += 1 while tree.get(j, i) > k
  r += i - j + 1
end
p r

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED