Submission #17038718

---

Source Code Expand

@file:Suppress("NOTHING_TO_INLINE", "EXPERIMENTAL_FEATURE_WARNING", "OVERRIDE_BY_INLINE")
//@file:OptIn(ExperimentalStdlibApi::class)

import java.io.PrintWriter
import java.util.TreeMap
import kotlin.math.*
import kotlin.random.Random
import kotlin.collections.sort as _sort
import kotlin.collections.sortDescending as _sortDescending
import kotlin.io.println as iprintln


/** @author Spheniscine */
fun main() { _writer.solve(); _writer.flush() }
fun PrintWriter.solve() {
//    val startTime = System.nanoTime()

    val numCases = 1//readInt()
    case@ for(case in 1..numCases) {
//        print("Case #$case: ")

        object {
            val n = readInt()
            val k = readInt()
            val A = readIntArray(n)
            val t = TreeMap<Int, Seg>()

            fun addSeg(l: Int, r: Int, s: Int) {
                t[r] = Seg(l, s)
            }

            init {
                var ans = 0
                for(a in A) {
                    val r = a+a+k+1
                    val l = a+a-k
                    var s = 1

                    while(true) {
                        val (ri: Int, seg: Seg) = t.higherEntry(l) ?: break
                        val (li, si) = seg
                        if(li >= r) break

                        t.remove(ri)

                        if(li < l) addSeg(li, l, si)
                        if(ri > r) addSeg(r, ri, si)
                        s = max(s, si+1)
                    }
                    addSeg(l, r, s)
                    ans = max(ans, s)
                }

                println(ans)
            }
        }
    }

//    iprintln("Time: ${(System.nanoTime() - startTime) / 1000000} ms")
}

data class Seg(val l: Int, val s: Int)

const val BILLION7 = 1e9.toInt() + 7
const val MOD = 998244353
const val TOTIENT = MOD - 1 // assumes MOD is prime

infix fun Int.modulo(mod: Int): Int = (this % mod).let { (it shr Int.SIZE_BITS - 1 and mod) + it }
infix fun Long.modulo(mod: Long) = (this % mod).let { (it shr Long.SIZE_BITS - 1 and mod) + it }
infix fun Long.modulo(mod: Int) = modulo(mod.toLong()).toInt()

fun Int.mulMod(other: Int, mod: Int) = toLong() * other modulo mod

fun Int.powMod(exponent: Long, mod: Int): Int {
    if(exponent < 0) error("Inverse not implemented")
    var res = 1L
    var e = exponent
    var b = modulo(mod).toLong()

    while(e > 0) {
        if(e and 1 == 1L) {
            res = res * b % mod
        }
        e = e shr 1
        b = b * b % mod
    }
    return res.toInt()
}
fun Int.powMod(exponent: Int, mod: Int) = powMod(exponent.toLong(), mod)
fun Int.modPowArray(n: Int, mod: Int): IntArray {
    val res = IntArray(n+1)
    res[0] = 1
    for(i in 1..n) res[i] = mulMod(res[i-1], mod)
    return res
}

inline fun Int.toModInt() = ModInt(this modulo MOD)
inline fun Long.toModInt() = ModInt(this modulo MOD)

/** note: Only use constructor for int within modulo range, otherwise use toModInt **/
inline class ModInt(val int: Int) {
    companion object {
        /** can't seem to make these private or inlined without causing compiler issues */
        @JvmField val _invMemo = HashMap<ModInt, ModInt>()
        fun _invMemoized(m: ModInt) = _invMemo.getOrPut(m) { m.inv_unmemoized() }
    }

    // normalizes an integer that's within range [-MOD, MOD) without branching
    private inline fun normalize(int: Int) = ModInt((int shr Int.SIZE_BITS - 1 and MOD) + int)

    operator fun plus(other: ModInt) = normalize(int + other.int - MOD) // overflow-safe even if MOD >= 2^30
    inline operator fun plus(other: Int) = plus(other.toModInt())
    operator fun inc() = normalize(int + (1 - MOD))

    operator fun minus(other: ModInt) = normalize(int - other.int)
    inline operator fun minus(other: Int) = minus(other.toModInt())
    operator fun dec() = normalize(int - 1)
    operator fun unaryMinus() = normalize(-int)

    operator fun times(other: ModInt) = ModInt((int.toLong() * other.int % MOD).toInt())
    inline operator fun times(other: Int) = ModInt(int.mulMod(other, MOD))

    fun pow(exponent: Int): ModInt {
        val e = if(exponent < 0) {
            require(int != 0) { "Can't invert/divide by 0" }
            exponent modulo TOTIENT
        } else exponent
        return ModInt(int.powMod(e, MOD))
    }

    fun pow(exponent: Long) = if(int == 0) when {
        exponent > 0 -> this
        exponent == 0L -> ModInt(1)
        else -> error("Can't invert/divide by 0")
    } else pow(exponent modulo TOTIENT)

    inline fun inverse() = inv_memoized() /** NOTE: Change if necessary */

    fun inv_unmemoized(): ModInt {
        require(int != 0) { "Can't invert/divide by 0" }
        return pow(TOTIENT - 1)
    }
    inline fun inv_memoized() = _invMemoized(this)

    operator fun div(other: ModInt) = times(other.inverse())
    inline operator fun div(other: Int) = div(other.toModInt())

    override inline fun toString() = int.toString()
}

inline operator fun Int.plus(modInt: ModInt) = modInt + this
inline operator fun Int.minus(modInt: ModInt) = toModInt() - modInt
inline operator fun Int.times(modInt: ModInt) = modInt * this
inline operator fun Int.div(modInt: ModInt) = modInt.inverse() * this

inline class ModIntArray(val intArray: IntArray): Collection<ModInt> {
    inline operator fun get(i: Int) = ModInt(intArray[i])
    inline operator fun set(i: Int, v: ModInt) { intArray[i] = v.int }

    override inline val size: Int get() = intArray.size
    inline val lastIndex get() = intArray.lastIndex
    inline val indices get() = intArray.indices

    override inline fun contains(element: ModInt): Boolean = element.int in intArray

    override fun containsAll(elements: Collection<ModInt>): Boolean = elements.all(::contains)

    override inline fun isEmpty(): Boolean = intArray.isEmpty()

    override fun iterator(): Iterator<ModInt> = object: Iterator<ModInt> {
        var index = 0
        override fun hasNext(): Boolean = index < size
        override fun next(): ModInt = get(index++)
    }

    fun copyOf(newSize: Int) = ModIntArray(intArray.copyOf(newSize))
    fun copyOf() = copyOf(size)
}
fun ModIntArray.copyInto(destination: ModIntArray, destinationOffset: Int = 0, startIndex: Int = 0, endIndex: Int = size) =
    ModIntArray(intArray.copyInto(destination.intArray, destinationOffset, startIndex, endIndex))
inline fun ModIntArray(size: Int) = ModIntArray(IntArray(size))
inline fun ModIntArray(size: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(size) { init(it).int })

fun ModInt.powArray(n: Int) = ModIntArray(int.modPowArray(n, MOD))

inline fun ModIntArray.first() = get(0)
inline fun ModIntArray.last() = get(lastIndex)
inline fun ModIntArray.joinToString(separator: CharSequence) = intArray.joinToString(separator)
inline fun <R> ModIntArray.fold(init: R, op: (acc: R, ModInt) -> R) = intArray.fold(init) { acc, i -> op(acc, ModInt(i)) }
inline fun <R> ModIntArray.foldRight(init: R, op: (ModInt, acc: R) -> R) = intArray.foldRight(init) { i, acc -> op(ModInt(i), acc) }
fun ModIntArray.sum() = fold(ModInt(0), ModInt::plus)
fun ModIntArray.product() = fold(ModInt(1), ModInt::times)

inline fun <T> Iterable<T>.sumByModInt(func: (T) -> ModInt) = fold(ModInt(0)) { acc, t -> acc + func(t) }
inline fun <T> Iterable<T>.productByModInt(func: (T) -> ModInt) = fold(ModInt(1)) { acc, t -> acc * func(t) }
inline fun <T> Sequence<T>.sumByModInt(func: (T) -> ModInt) = fold(ModInt(0)) { acc, t -> acc + func(t) }
inline fun <T> Sequence<T>.productByModInt(func: (T) -> ModInt) = fold(ModInt(1)) { acc, t -> acc * func(t) }
inline fun <T> Array<T>.sumByModInt(func: (T) -> ModInt) = fold(ModInt(0)) { acc, t -> acc + func(t) }
inline fun <T> Array<T>.productByModInt(func: (T) -> ModInt) = fold(ModInt(1)) { acc, t -> acc * func(t) }
fun Iterable<ModInt>.sum() = sumByModInt { it }
fun Sequence<ModInt>.sum() = sumByModInt { it }
fun Iterable<ModInt>.product() = productByModInt { it }
fun Sequence<ModInt>.product() = productByModInt { it }
fun Collection<ModInt>.toModIntArray() = ModIntArray(size).also { var i = 0; for(e in this) { it[i++] = e } }



/** IO */
//@JvmField val INPUT = File("input.txt").inputStream()
//@JvmField val OUTPUT = File("output.txt").outputStream()
@JvmField val INPUT = System.`in`
@JvmField val OUTPUT = System.out

const val _BUFFER_SIZE = 1 shl 16
@JvmField val _buffer = ByteArray(_BUFFER_SIZE)
@JvmField var _bufferPt = 0
@JvmField var _bytesRead = 0

tailrec fun readChar(): Char {
    if(_bufferPt == _bytesRead) {
        _bufferPt = 0
        _bytesRead = INPUT.read(_buffer, 0, _BUFFER_SIZE)
    }
    return if(_bytesRead < 0) Char.MIN_VALUE
    else {
        val c = _buffer[_bufferPt++].toChar()
        if (c == '\r') readChar()
        else c
    }
}

fun readLine(): String? {
    var c = readChar()
    return if(c == Char.MIN_VALUE) null
    else buildString {
        while(c != '\n' && c != Char.MIN_VALUE) {
            append(c)
            c = readChar()
        }
    }
}
fun readLn() = readLine()!!

fun read() = buildString {
    var c = readChar()
    while(c <= ' ') {
        if(c == Char.MIN_VALUE) return@buildString
        c = readChar()
    }
    do {
        append(c)
        c = readChar()
    } while(c > ' ')
}
fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readLines(n: Int) = List(n) { readLn() }
fun readInts(n: Int) = List(n) { read().toInt() }
fun readIntArray(n: Int) = IntArray(n) { read().toInt() }
fun readDoubles(n: Int) = List(n) { read().toDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { read().toDouble() }
fun readLongs(n: Int) = List(n) { read().toLong() }
fun readLongArray(n: Int) = LongArray(n) { read().toLong() }

@JvmField val _writer = PrintWriter(OUTPUT, false)

/** shuffles and sort overrides to avoid quicksort attacks */
private inline fun <T> _shuffle(rnd: Random, get: (Int) -> T, set: (Int, T) -> Unit, size: Int) {
    // Fisher-Yates shuffle algorithm
    for (i in size - 1 downTo 1) {
        val j = rnd.nextInt(i + 1)
        val temp = get(i)
        set(i, get(j))
        set(j, temp)
    }
}

@JvmField var _random: Random? = null
val random get() = _random ?: Random(0x594E215C123 * System.nanoTime()).also { _random = it }

fun IntArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun IntArray.sort() { shuffle(); _sort() }
fun IntArray.sortDescending() { shuffle(); _sortDescending() }

fun LongArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun LongArray.sort() { shuffle(); _sort() }
fun LongArray.sortDescending() { shuffle(); _sortDescending() }

fun DoubleArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun DoubleArray.sort() { shuffle(); _sort() }
fun DoubleArray.sortDescending() { shuffle(); _sortDescending() }

fun CharArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
inline fun CharArray.sort() { _sort() }
inline fun CharArray.sortDescending() { _sortDescending() }

inline fun <T: Comparable<T>> Array<out T>.sort() = _sort()
inline fun <T: Comparable<T>> Array<out T>.sortDescending() = _sortDescending()
inline fun <T: Comparable<T>> MutableList<out T>.sort() = _sort()
inline fun <T: Comparable<T>> MutableList<out T>.sortDescending() = _sortDescending()

fun `please stop removing these imports IntelliJ`() { iprintln(max(1, 2)) }

/** additional commons */
inline fun <T> Iterable<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Sequence<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Array<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
fun IntArray.sumLong() = fold(0L, Long::plus)

Submission Info

Compile Error

warning: ATTENTION!
This build uses unsafe internal compiler arguments:

-XXLanguage:+InlineClasses

This mode is not recommended for production use,
as no stability/compatibility guarantees are given on
compiler or generated code. Use it at your own risk!

Judge Result