結果
問題 | No.1300 Sum of Inversions |
ユーザー |
|
提出日時 | 2022-01-10 21:43:01 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 1,444 ms / 2,000 ms |
コード長 | 1,439 bytes |
コンパイル時間 | 16,607 ms |
コンパイル使用メモリ | 449,548 KB |
実行使用メモリ | 125,716 KB |
最終ジャッジ日時 | 2024-11-14 11:07:49 |
合計ジャッジ時間 | 60,544 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
Main.kt:26:9: warning: variable 'n' is never used val n = readLine()!!.trim().toInt() ^
ソースコード
const val MOD = 998244353class Bit(val size: Int) {private val vec = IntArray(size)fun get(position: Int): Int {var result = 0var pos = positionwhile (pos in vec.indices) {result = (result + vec[pos]) % MODpos -= pos.inv() and (pos + 1)}return result}fun add(position: Int, value: Int) {var pos = positionwhile (pos in vec.indices) {vec[pos] = (vec[pos] + value) % MODpos += pos.inv() and (pos + 1)}}fun add(position: Int, value: Long) {return add(position, (value % MOD).toInt())}}fun main() {val n = readLine()!!.trim().toInt()val num = readLine()!!.trim().split(' ').map(String::toInt)val rank = num.distinct().sorted().let { list -> list.indices.associateBy { list[it] }}val sumBits = Array(2){Bit(rank.size)}val countBits = Array(2){Bit(rank.size)}var result = 0Lfor (a in num.reversed()) {val i = rank[a]!!val sum2 = sumBits[1].get(i - 1)val count2 = countBits[1].get(i - 1)result = (result + sum2 + count2.toLong() * a) % MODval sum1 = sumBits[0].get(i - 1)val count1 = countBits[0].get(i - 1)sumBits[1].add(i, sum1 + count1.toLong() * a)countBits[1].add(i, count1)sumBits[0].add(i, a)countBits[0].add(i, 1)}println(result)}