Submission #53362331

---

Source Code Expand

import java.io.*
import java.util.*
import java.util.function.IntPredicate
import kotlin.collections.*
import kotlin.math.max

val INPUT: InputStream = System.`in`
val OUTPUT: PrintStream = System.out

val _reader = INPUT.bufferedReader()

var _tokenizer: StringTokenizer = StringTokenizer("")
fun read(): String {
    while (!_tokenizer.hasMoreTokens()) {
        _tokenizer = StringTokenizer(_reader.readLine() ?: return "", " ")
    }
    return _tokenizer.nextToken()
}

fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readInts(n: Int) = List(n) { readInt() }
fun readIntArray(n: Int) = IntArray(n) { readInt() }
fun readDoubles(n: Int) = List(n) { readDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { readDouble() }
fun readLongs(n: Int) = List(n) { readLong() }
fun readLongArray(n: Int) = LongArray(n) { readLong() }

val _writer = PrintWriter(OUTPUT, false)
inline fun output(block: PrintWriter.() -> Unit) {
    _writer.apply(block).flush()
}

class MutableIntMap<K> : LinkedHashMap<K, Int>() {
    override operator fun get(key: K): Int = super.get(key) ?: 0

    fun increment(key: K, value: Int = 1) {
        this[key] = this[key] + value
    }

    companion object {
        fun <K> mutableIntMapOf(vararg pairs: Pair<K, Int>) =
            MutableIntMap<K>().apply { putAll(pairs) }
    }
}

typealias Pii = Pair<Int, Int>

fun readPii() = readInt() to readInt()
fun readPiis(n: Int) = List(n) { readPii() }

infix fun Int.hasBit(i: Int): Boolean = this and (1 shl i) > 0
infix fun Int.xorBit(i: Int): Int = this xor (1 shl i)
infix fun Long.hasBit(i: Int): Boolean = this and (1L shl i) > 0
infix fun Long.xorBit(i: Int): Long = this xor (1L shl i)

fun largerStackSize(stackSizeMegaBytes: Int = 100, action: () -> Unit) {
    Thread(null, action, "", 1024L * 1024 * stackSizeMegaBytes).apply {
        start()
        join()
    }
}

// #################################################################################################

class SimpleSegmentTree<T>(
    private val n: Int,
    private val identity: T,
    private val combine: (T, T) -> T,
) {
    private val tree = MutableList(2 * n) { identity }

    constructor(values: List<T>, identity: T, combine: (T, T) -> T) :
            this(values.size, identity, combine) {
        values.forEachIndexed { i, v -> tree[i + n] = v }
        for (i in n - 1 downTo 1) tree[i] = combine(tree[i * 2], tree[i * 2 + 1])
    }

    /** Queries for the range `[l, r)`. */
    fun query(l: Int, r: Int): T {
        var resL = identity
        var resR = identity
        var i = l + n
        var j = r + n
        while (i < j) {
            if (i and 1 > 0) resL = combine(resL, tree[i++])
            if (j and 1 > 0) resR = combine(tree[--j], resR)
            i /= 2
            j /= 2
        }
        return combine(resL, resR)
    }

    fun update(p: Int, transform: (T) -> T) {
        var i = p + n
        tree[i] = transform(tree[i])
        while (i > 1) {
            i /= 2
            tree[i] = combine(tree[i * 2], tree[i * 2 + 1])
        }
    }
}

fun solve() {
    val n = readInt()
    val c = readLong()
    val maxL = SimpleSegmentTree(n, identity = Long.MIN_VALUE / 2, combine = ::max)
    val maxR = SimpleSegmentTree(n, identity = Long.MIN_VALUE / 2, combine = ::max)
    maxL.update(0) { 0 }
    maxR.update(0) { 0 }

    repeat(readInt()) {
        val t = readInt() - 1
        val p = readLong()
        val m = p + max(maxL.query(0, t + 1) - t * c, maxR.query(t, n) + t * c)
//        println("! $t $m")
        if (m + t * c > maxL.query(t, t + 1)) {
            maxL.update(t) { m + t * c }
        }
        if (m - t * c > maxR.query(t, t + 1)) {
            maxR.update(t) { m - t * c }
        }
    }
    val ans = (0 until n).maxOf { maxL.query(it, it + 1) - it * c }
    println(ans)
}

fun main() {
//    repeat(readInt()) { solve() }
    solve()
}

Submission Info

Judge Result