結果
問題 | No.1300 Sum of Inversions |
ユーザー | Shibuyap |
提出日時 | 2021-02-06 05:08:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,757 bytes |
コンパイル時間 | 2,507 ms |
コンパイル使用メモリ | 208,056 KB |
実行使用メモリ | 13,336 KB |
最終ジャッジ日時 | 2023-09-15 11:15:49 |
合計ジャッジ時間 | 8,344 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 104 ms
10,304 KB |
testcase_04 | AC | 98 ms
10,172 KB |
testcase_05 | AC | 84 ms
8,880 KB |
testcase_06 | AC | 114 ms
11,216 KB |
testcase_07 | AC | 110 ms
10,792 KB |
testcase_08 | AC | 121 ms
11,624 KB |
testcase_09 | AC | 122 ms
11,616 KB |
testcase_10 | AC | 67 ms
7,976 KB |
testcase_11 | AC | 68 ms
7,948 KB |
testcase_12 | AC | 100 ms
10,020 KB |
testcase_13 | AC | 98 ms
10,248 KB |
testcase_14 | AC | 130 ms
12,220 KB |
testcase_15 | AC | 121 ms
11,476 KB |
testcase_16 | AC | 103 ms
10,636 KB |
testcase_17 | AC | 65 ms
7,880 KB |
testcase_18 | AC | 76 ms
8,380 KB |
testcase_19 | AC | 89 ms
9,264 KB |
testcase_20 | AC | 91 ms
9,464 KB |
testcase_21 | AC | 92 ms
9,492 KB |
testcase_22 | AC | 83 ms
8,820 KB |
testcase_23 | AC | 112 ms
11,140 KB |
testcase_24 | AC | 83 ms
9,060 KB |
testcase_25 | AC | 72 ms
8,220 KB |
testcase_26 | AC | 71 ms
8,148 KB |
testcase_27 | AC | 79 ms
8,808 KB |
testcase_28 | AC | 125 ms
11,952 KB |
testcase_29 | AC | 87 ms
9,464 KB |
testcase_30 | AC | 120 ms
11,536 KB |
testcase_31 | AC | 81 ms
9,088 KB |
testcase_32 | AC | 84 ms
9,140 KB |
testcase_33 | AC | 56 ms
13,336 KB |
testcase_34 | AC | 109 ms
13,316 KB |
testcase_35 | AC | 89 ms
12,812 KB |
testcase_36 | WA | - |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); ++i) #define srep(i,s,t) for(int i = s; i < t; ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) using namespace std; typedef long long int ll; typedef pair<ll,ll> P; #define yn {puts("Yes");}else{puts("No");} #define MAX_N 200005 const ll MOD = 998244353; // long long version ll bit[MAX_N+1][2]; int nn = MAX_N; // 1-index void adds(int a, ll w, int idx){ for(int x = a; x <= nn; x += x & -x) bit[x][idx] += w; } // bit[1,a]の和を返す. ll sums(int a, int idx){ ll ret = 0; for(int x = a; x > 0; x -= x & -x) ret += bit[x][idx]; return ret; } int main() { ll n; cin >> n; ll a[n+1] = {}; srep(i,1,n+1) cin >> a[i]; ll sum[n+1] = {}; srep(i,1,n+1) sum[i] = sum[i-1] + a[i]; vector<P> v(n); srep(i,1,n+1){ v[i-1].first = a[i]; v[i-1].second = i; } sort(v.begin(), v.end(),greater<P>()); ll ans = 0; rep(i,n){ ll x = v[i].first; vector<int> keep; while(i<n&&v[i].first==x){ keep.push_back(v[i].second); i++; } reverse(keep.begin(), keep.end()); rep(j,keep.size()){ int y = keep[j]; ll left = sums(y,1) - j; ll right = n - y - (sums(n,1) - sums(y,1)) - (keep.size()-1-j); ans += x * left % MOD * right % MOD; ll sumleft = sums(y,0) - x*j; ll sumright = sum[n] - sum[y] - (sums(n,0) - sums(y,0)) - x*(keep.size()-1-j); ans += sumleft * right % MOD; ans += sumright * left % MOD; ans %= MOD; adds(y,x,0); adds(y,1,1); } i--; } cout << ans << endl; return 0; }