フェンウィック ツリー データ構造を使用して、コードフォースに関するマルチセットの質問 ( https://codeforces.com/contest/1354/problem/D )を解決しようとしていました。サンプル テスト ケースには合格しましたが、サブミット後にメモリ制限エラーが発生しました。テストケースは以下のとおりです。(基本的に、テストケースは次のとおりです。
1000000 1000000
1......................1 //10^6 回
-1..........-1 //10^6 回)。
IDE で同様のテストケースを試したところ、以下のエラーが発生しました。(上記と同様に、私が提供したテストケースは次のとおりです。
1000000 1
1......................1 //10^6 回
-1
)
スレッド「メイン」での例外 java.lang.IndexOutOfBoundsException: java.base/jdk.internal の java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) で、長さ 524289 の範囲外のインデックス 524289。 java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) の util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) 373) MultisetKt.main(multiset.kt:47) で java.base/java.util.ArrayList.get(ArrayList.java:426) で MultisetKt.main(multiset.kt) で
これが私のコードです:
private fun readInt() = readLine()!!.split(" ").map { it.toInt() }
fun main() {
var (n, q) = readInt()
var list = readInt() //modify the list to store it from index 1
var finalList = listOf(0) + list
val query = readInt()
var bit = MutableList(n+1){0}
fun update(i:Int, value:Int) {
var index = i
while(index < n){
bit.set (index , bit[index] + value)
index += (index and -index)
}
}
fun rangefunc(i:Int): Int {
var su = 0
var index = i
while(index > 0){
su += bit[index]
index -= (index and -index)
}
return su
}
fun find(x:Int):Int {
var l = 1
var r = n
var ans = n
var mid = 0
while (l <= r) {
mid = (l + r) / 2
if (rangefunc(mid) >= x) {
ans = mid
r = mid - 1
} else {
l = mid + 1
}
}
return ans
}
for (i in 1..n) {
update(finalList[i], 1)
}
for (j in 0..q - 1) {
if (query[j] > 0) {
update(query[j], 1)
} else {
update(find(-query[j]), -1)
}
}
if(rangefunc(n) == 0){
println(0)
}else{
println(find(1))
}
}
これは、BITlist が 10^6 要素を格納できないためだと思いますが、確かではありません。コードにどのような変更を加える必要があるか、また将来そのような場合に対処する方法についての追加のアドバイスを教えてください。
前もって感謝します :)