結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2018-02-03 20:19:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 371 ms / 3,000 ms |
コード長 | 636 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 47,684 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-06-30 03:54:01 |
合計ジャッジ時間 | 5,267 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <cstdio>#include <algorithm>using namespace std;int n, a[500009], p[500009], v[500009], bit[500009]; long long val;int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]), p[i] = i, v[i] = a[i];sort(p, p + n, [](int i, int j) { return a[i] != a[j] ? a[i] > a[j] : i > j; });sort(v, v + n);for (int i = 0; i < n; i++) {for (int j = p[i]; j >= 1; j -= j & (-j)) val += bit[j];for (int j = p[i] + 1; j <= n; j += j & (-j)) bit[j]++;}for (int i = 0; i < n; i++) {printf("%lld\n", val);val += n - (lower_bound(v, v + n, a[i]) - v) - (upper_bound(v, v + n, a[i]) - v);}return 0;}