結果
問題 | No.1300 Sum of Inversions |
ユーザー |
|
提出日時 | 2020-11-27 22:08:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 551 ms / 2,000 ms |
コード長 | 2,724 bytes |
コンパイル時間 | 1,266 ms |
コンパイル使用メモリ | 105,116 KB |
実行使用メモリ | 24,320 KB |
最終ジャッジ日時 | 2024-07-26 12:59:57 |
合計ジャッジ時間 | 15,862 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>#include <functional>#include <limits>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 998244353;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;template<typename T>class segment_tree{int n;T fval;function<T(T,T)> operation;vector<T> dat;T _query(int a, int b, int k, int l, int r){if(r <= a || b <= l){return fval;}if(a <= l && r <= b){return dat[k];}else {T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2 );T vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);return operation(vl, vr);}}public:segment_tree(){}segment_tree(int n_, T val, function<T(T,T)> fun){init(n_, val, fun);}~segment_tree(){}void init(int n_, T val, function<T(T,T)> fun){fval = val;operation = fun;n = 1;while(n < n_) n *= 2;dat.resize(2 * n - 1);for(int i = 0; i < 2 * n - 1; i++) dat[i] = fval;}void update(int k, T a){k += n - 1;dat[k] += a;while(k > 0){k = (k - 1) / 2;dat[k] = operation(dat[k*2 + 1],dat[k*2 + 2]);}}T query(int a, int b){return _query(a, b, 0, 0, n);}};signed main(){cout<<fixed<<setprecision(10);int N;int ans = 0;vector<int> A, B, C;segment_tree<int> segl, segr;segment_tree<int> segl2, segr2;cin>>N;A.resize(N);B.resize(N);C.resize(N);segl.init(N+1,0, [](int first, int second){ return (first+second);});segr.init(N+1,0, [](int first, int second){ return (first+second);});segl2.init(N+1,0, [](int first, int second){ return (first+second);});segr2.init(N+1,0, [](int first, int second){ return (first+second);});for(int i = 0; i < N; i++){cin>>A[i];}B = A;C = A;sort(B.begin(), B.end());for(int i = 0; i < N; i++){C[i] = lower_bound(B.begin(), B.end(),A[i]) - B.begin();segr.update(C[i], 1);segr2.update(C[i], A[i]);}for(int i = 0; i < N; i++){segr.update(C[i], -1);segr2.update(C[i], -A[i]);ans += segl.query(C[i]+1,N)%MOD * (segr.query(0, C[i])%MOD) % MOD * A[i] % MOD;ans += segl.query(C[i]+1,N)%MOD * (segr2.query(0, C[i])%MOD) % MOD;ans += segl2.query(C[i]+1,N)%MOD * (segr.query(0, C[i])%MOD) % MOD;ans %= MOD;// cout<<i<<" "<<ans<<endl;segl.update(C[i], 1);segl2.update(C[i], A[i]);}cout<<ans<<endl;return 0;}