結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
|
提出日時 | 2022-02-13 12:00:40 |
言語 | TypeScript (5.7.2) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,053 bytes |
コンパイル時間 | 8,381 ms |
コンパイル使用メモリ | 228,556 KB |
実行使用メモリ | 43,392 KB |
最終ジャッジ日時 | 2024-12-31 16:44:55 |
合計ジャッジ時間 | 11,297 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import * as fs from "fs" class BinaryIndexedTree { data: number[] size: number constructor(size: number) { this.size = size this.data = Array(size).fill(0) } public add(p: number, x: number): void { p++; while (p <= this.size) { this.data[p - 1] += x; p += p & -p } } public range_sum(l: number, r: number): number { return this.sum(r) - this.sum(l) } private sum(p: number): number { let res = 0 while (p > 0) { res += this.data[p - 1] p -= p & -p } return res } } type Input = (args: string) => void const main: Input = args => { const input = args.trim().split("\n"); const n = +input.shift() const p = input.shift().split(" ").map(x => +x) const bit = new BinaryIndexedTree(n + 1); let ans = 0 p.forEach(x => { ans += bit.range_sum(x + 1, n + 1) bit.add(x, 1) }) console.log(ans) } main(fs.readFileSync('/dev/stdin', 'utf8'));