# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
886041 | CDuong | Sum Zero (RMI20_sumzero) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import kotlin.math.*
import java.util.Vector
private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readLong() = readLn().toLong()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
private fun readLongs() = readStrings().map { it.toLong() }
fun main() {
var n = readInt()
var a = readInts()
var i: Int = 0
i = 1
var cope = Array(6) { 1 }
while (i < 6) {
cope[i] = cope[i - 1] * 10
i++
}
var nxt = Array(6) { Array<Int>(n + 2) { n + 1 } }
var mp = mutableMapOf<Long, Int>()
mp[0] = 0
i = 0
var cur_sum: Long = 0
while (i < n) {
cur_sum += a[i]
if (mp[cur_sum] != null) {
// println(mp[cur_sum])
nxt[0][mp[cur_sum]!!] = i + 1
}
mp[cur_sum] = i + 1;
i++;
}
i = n;
while (i >= 0) {
nxt[0][i] = min(nxt[0][i], nxt[0][i + 1])
i--
}
i = 1
var j = 0
while (i < 6) {
j = 0
while (j < n) {
nxt[i][j] = nxt[i - 1][nxt[i - 1][nxt[i - 1][nxt[i - 1][nxt[i - 1][j]]]]]
// println("${i}, ${j}, ${nxt[i][j]}")
j++
}
i++;
}
var q = readInt()
repeat(q) {
var (l, r) = readInts()
l--
var res = 0
i = 5
while (i >= 0 && l < n) {
while (nxt[i][l] <= r) {
res += cope[i]
l = nxt[i][l]
}
i--
}
println(res)
}
// i = 0
// while (i < n) {
// println(nxt[0][i])
// i++
// }
}