結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー | kyuna |
提出日時 | 2019-07-27 18:21:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,068 ms / 3,000 ms |
コード長 | 1,383 bytes |
コンパイル時間 | 817 ms |
コンパイル使用メモリ | 77,912 KB |
実行使用メモリ | 11,248 KB |
最終ジャッジ日時 | 2023-09-15 06:25:20 |
合計ジャッジ時間 | 8,808 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 762 ms
11,092 KB |
testcase_08 | AC | 935 ms
10,980 KB |
testcase_09 | AC | 1,043 ms
11,016 KB |
testcase_10 | AC | 765 ms
11,248 KB |
testcase_11 | AC | 1,068 ms
11,124 KB |
testcase_12 | AC | 1,032 ms
10,924 KB |
testcase_13 | AC | 2 ms
4,380 KB |
ソースコード
#include <algorithm> #include <iostream> #include <vector> using namespace std; template <typename Abel> struct BIT { const Abel UNITY_SUM = 0; vector<Abel> dat; BIT(int n) : dat(n + 1, UNITY_SUM) { } // [1, n] inline void add(int i, Abel x) { while (i < dat.size()) { dat[i] += x; i += i & -i; } } inline Abel sum(int i) { // [1, i] Abel res = UNITY_SUM; while (i > 0) { res += dat[i]; i -= i & -i; } return res; } inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); } // [a, b) /* debug */ Abel operator[](int i) { return sum(i, i + 1); } void debug() { for (int i = 1; i < dat.size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; int main() { int n; cin >> n; vector<int> a(n); for (int &ai: a) cin >> ai; vector<int> b = a; sort(begin(b), end(b)); b.erase(unique(begin(b), end(b)), end(b)); long long res = 0; BIT<int> bit(n); vector<int> order(n); for (int i = 0; i < n; i++) { order[i] = lower_bound(begin(b), end(b), a[i]) - begin(b) + 1; res += bit.sum(order[i] + 1, n + 1); bit.add(order[i], 1); } cout << res << endl; for (int i = 0; i < n - 1; i++) { res -= bit.sum(1, order[i]); res += bit.sum(order[i] + 1, n + 1); cout << res << endl; } return 0; }