結果
問題 | No.1300 Sum of Inversions |
ユーザー | Shibuyap |
提出日時 | 2021-02-06 05:10:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 2,017 ms |
コンパイル使用メモリ | 205,400 KB |
最終ジャッジ日時 | 2025-01-18 13:20:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#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); sumleft %= MOD; sumright %= MOD; ans += sumleft * right % MOD; ans += sumright * left % MOD; ans %= MOD; adds(y,x,0); adds(y,1,1); } i--; } cout << ans << endl; return 0; }