結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2018-10-06 07:50:56 |
言語 | Scala(Beta) (3.6.2) |
結果 |
AC
|
実行時間 | 1,364 ms / 2,500 ms |
コード長 | 1,094 bytes |
コンパイル時間 | 9,784 ms |
コンパイル使用メモリ | 274,932 KB |
実行使用メモリ | 75,308 KB |
最終ジャッジ日時 | 2024-07-01 04:47:40 |
合計ジャッジ時間 | 28,353 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
import scala.math._import scala.collection.mutable._import scala.collection.immutable._object Main{def main(args: Array[String]): Unit = {val sc = new java.util.Scanner(System.in)val pw = new java.io.PrintWriter(System.out)val n = sc.nextIntval ms = Array.fill(n)(sc.nextInt)val bit = new BIT(30000)val c = ms.reverse.map(m => {val a = bit.get(m);bit.update(m, 1)a}).sumpw.println(c);pw.flush()}}class BIT(val n: Int){private var tree: Array[Int] = Array.fill(n+1)(0) //1-index (1..n)def init(): Unit = {tree = Array.fill(n+1)(0)}def update(x: Int, a: Int): Unit = {var i: Int = xwhile (i <= n){tree(i) = tree(i) + a; i += (i & (-i))}}def get(x: Int): Int = {var i: Int = xvar a: Int = 0while (i > 0){a += tree(i); i -= (i & (-i))}a}def lower_bound(i: Int): Int = {var w = ivar k: Int = 1var x: Int = 0while (k*2 <= n) k *= 2while (k > 0){if (x+k <= n && tree(x+k) < w) {w -= tree(x+k); x += k}k /= 2}x+1}}