結果

問題 No.742 にゃんにゃんにゃん 猫の挨拶
ユーザー HaarHaar
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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.nextInt
val 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
}).sum
pw.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 = x
while (i <= n){tree(i) = tree(i) + a; i += (i & (-i))}
}
def get(x: Int): Int = {
var i: Int = x
var a: Int = 0
while (i > 0){a += tree(i); i -= (i & (-i))}
a
}
def lower_bound(i: Int): Int = {
var w = i
var k: Int = 1
var x: Int = 0
while (k*2 <= n) k *= 2
while (k > 0){
if (x+k <= n && tree(x+k) < w) {w -= tree(x+k); x += k}
k /= 2
}
x+1
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0