結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
|
提出日時 | 2022-02-13 17:23:38 |
言語 | JavaScript (node v23.5.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 128 ms |
コンパイル使用メモリ | 6,948 KB |
実行使用メモリ | 45,164 KB |
最終ジャッジ日時 | 2024-06-29 05:43:01 |
合計ジャッジ時間 | 3,119 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
"use strict"; exports.__esModule = true; var fs = require("fs"); var BinaryIndexedTree = function (n) { var data = Array(n).fill(0); var add = function (p, x) { p++; var n = data.length; while (p <= n) { data[p - 1] += x; p += p & -p; } }; var sum = function (p) { var res = 0; while (p > 0) { res += data[p - 1]; p -= p & -p; } return res; }; var rangeSum = function (l, r) { return sum(r) - sum(l); }; return { add: add, sum: sum, rangeSum: rangeSum }; }; var main = function (args) { var input = args.trim().split("\n"); var n = +input.shift(); var p = input.shift().split(" ").map(function (x) { return +x; }); var bit = BinaryIndexedTree(n + 1); var ans = 0; p.forEach(function (x) { ans += bit.rangeSum(x + 1, n + 1); bit.add(x, 1); }); console.log(ans); }; main(fs.readFileSync('/dev/stdin', 'utf8'));