Untitled

mail@pastecode.io avatar
unknown
kotlin
a year ago
1.6 kB
5
Indexable
Never
    import java.io.BufferedReader
    import java.io.BufferedWriter
    import java.io.InputStreamReader
    import java.io.OutputStreamWriter
    import java.util.*
     
    fun main() {
        val output = BufferedWriter(OutputStreamWriter(System.out))
        val input = BufferedReader(InputStreamReader(System.`in`))
     
        val inp = input.readLine().split(" ")
        val N = inp[0].toInt()
        val K = inp[1].toLong()
        val nums = input.readLine().split(" ").map { it.toLong() }
     
        var left = 0
        var right = 0
        var goodSegments = 0L
        val maxStack = LinkedList<Int>()
        val minStack = LinkedList<Int>()
     
        while (right < N) {
            while (maxStack.isNotEmpty() && nums[right] >= nums[maxStack.peekLast()]) {
                maxStack.removeLast()
            }
            maxStack.addLast(right)
            while (minStack.isNotEmpty() && nums[right] <= nums[minStack.peekLast()]) {
                minStack.removeLast()
            }
            minStack.addLast(right)
     
            while (left <= right && nums[maxStack.peekFirst()] - nums[minStack.peekFirst()] > K) {
                if (left == maxStack.peekFirst()) {
                    maxStack.removeFirst()
                }
                if (left == minStack.peekFirst()) {
                    minStack.removeFirst()
                }
                left++
            }
     
            goodSegments += right - left + 1
            right++
        }
     
        output.write("$goodSegments\n")
        output.close()
        input.close()
    }