結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
|
提出日時 | 2020-08-20 04:57:12 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 528 ms / 2,000 ms |
コード長 | 1,650 bytes |
コンパイル時間 | 15,857 ms |
コンパイル使用メモリ | 444,136 KB |
実行使用メモリ | 77,232 KB |
最終ジャッジ日時 | 2024-10-12 18:41:34 |
合計ジャッジ時間 | 32,857 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.io.PrintWriter import java.util.* class BIT(n: Int) { private val N = if (Integer.highestOneBit(n) == n) n else Integer.highestOneBit(n) shl 1 private val bit = LongArray(N + 1) fun sum(i: Int): Long { var x = i var s = 0L while(x > 0) { s += bit[x] x -= x and -x } return s } fun add(i: Int, a: Long) { var x = i + 1 while(x <= N) { bit[x] += a x += x and -x } } } fun PrintWriter.solve(sc: FastScanner) { val n = sc.nextInt() val a = Array(n) { sc.nextInt() } val b = Array(n) { sc.nextInt() } val new = Array(n + 1) { 0 } for (i in 0 until n) { new[b[i]] = i + 1 } for (i in 0 until n) { a[i] = new[a[i]] } val bit = BIT(n) var ans = 0L for (i in 0 until n) { ans += i - bit.sum(a[i]) bit.add(a[i], 1) } println(ans) } fun main() { val writer = PrintWriter(System.out, false) writer.solve(FastScanner(System.`in`)) writer.flush() } class FastScanner(s: InputStream) { private var st = StringTokenizer("") private val br = BufferedReader(InputStreamReader(s)) fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine() fun nextDouble() = next().toDouble() fun ready() = br.ready() }