結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
ユーザー HaarHaar
提出日時 2018-10-06 07:50:56
言語 Scala(Beta)
(3.4.0)
結果
AC  
実行時間 1,342 ms / 2,500 ms
コード長 1,094 bytes
コンパイル時間 12,611 ms
コンパイル使用メモリ 259,660 KB
実行使用メモリ 68,172 KB
最終ジャッジ日時 2023-09-13 20:18:51
合計ジャッジ時間 28,145 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 991 ms
63,280 KB
testcase_01 AC 991 ms
63,296 KB
testcase_02 AC 984 ms
63,244 KB
testcase_03 AC 991 ms
63,228 KB
testcase_04 AC 1,012 ms
63,280 KB
testcase_05 AC 1,020 ms
63,708 KB
testcase_06 AC 1,062 ms
63,812 KB
testcase_07 AC 1,100 ms
63,508 KB
testcase_08 AC 1,121 ms
63,844 KB
testcase_09 AC 988 ms
63,268 KB
testcase_10 AC 995 ms
63,292 KB
testcase_11 AC 1,342 ms
66,636 KB
testcase_12 AC 1,323 ms
68,172 KB
testcase_13 AC 986 ms
63,312 KB
testcase_14 AC 984 ms
63,384 KB
testcase_15 AC 1,003 ms
63,648 KB
権限があれば一括ダウンロードができます

ソースコード

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
  }
}
0