Submission #53621281

---

Source Code Expand

import java.io.*
import java.util.*
import kotlin.collections.*

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()
    }
}

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

val M = listOf(
    listOf(2, 1, 2, 1),
    listOf(1, 2, 1, 2),
    listOf(0, 1, 0, 1),
    listOf(1, 0, 1, 0),
    listOf(2, 1, 2, 1),
    listOf(1, 2, 1, 2),
    listOf(0, 1, 0, 1),
    listOf(1, 0, 1, 0),
)

class RangeSum2D(values: List<List<Int>>) {
    private val n = values.size
    private val m = values[0].size
    private val sum = Array(n) { LongArray(m) }
    private fun sum(i: Int, j: Int) = sum.getOrNull(i)?.getOrNull(j) ?: 0

    fun rangeSum(bottom: Int, right: Int): Long {
        check(bottom in 0..n && right in 0..m)
        return sum(bottom - 1, right - 1)
    }

    /** Queries the sum of the range. */
    fun rangeSum(top: Int, left: Int, bottom: Int, right: Int): Long {
        check(top in 0..bottom && bottom <= n)
        check(left in 0..right && right <= m)
        return rangeSum(bottom, right) - rangeSum(top, right) - rangeSum(bottom, left) + rangeSum(top, left)
    }

    fun rangeSumTile(bottom: Int, right: Int): Long {
        check(bottom >= 0 && right >= 0)
        if (bottom <= n && right <= m) return rangeSum(bottom, right)
        val a = bottom / n
        val i = bottom % n
        val b = right / m
        val j = right % m
        return rangeSum(n, m) * a * b + rangeSum(i, m) * b + rangeSum(n, j) * a + rangeSum(i, j)
    }

    fun rangeSumTile(top: Int, left: Int, bottom: Int, right: Int): Long {
        check(top in 0..bottom && left in 0..right)
        return rangeSumTile(bottom, right) -
                rangeSumTile(top, right) -
                rangeSumTile(bottom, left) +
                rangeSumTile(top, left)
    }

    init {
        for (i in 0 until n) for (j in 0 until m) {
            sum[i][j] = sum(i - 1, j) + sum(i, j - 1) - sum(i - 1, j - 1) + values[i][j]
        }
    }
}

val Sum = RangeSum2D(M)

fun dfs(a: Long, b: Long): Long {
    if (a <= 4 && b <= 2) return Sum.rangeSum(a.toInt(), b.toInt())
    val a0 = a / 4
    val b0 = b / 2
    if (a0 > 0) {
        return if (b0 > 0) {
            dfs(a % 4, b) + (8 * b0 + dfs(4, b % 2)) * a0
        } else {
            dfs(a % 4, b) + Sum.rangeSum(4, b.toInt()) * a0
        }
    }
    return (dfs(a, b % 2) + Sum.rangeSum(a.toInt(), 2) * b0)
}

fun dfs(a: Long, b: Long, c: Long, d: Long): Long {
    return dfs(c, d) - dfs(c, b) - dfs(a, d) + dfs(a, b)
}

fun solve() {
    val a = readLong() + 1000000000
    val b = readLong() + 1000000000
    val c = readLong() + 1000000000
    val d = readLong() + 1000000000
    println(dfs(a, b, c, d))
}

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

Submission Info

Judge Result