結果
問題 | No.1300 Sum of Inversions |
ユーザー | ocvret_ |
提出日時 | 2020-11-27 22:59:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 712 ms / 2,000 ms |
コード長 | 2,169 bytes |
コンパイル時間 | 2,228 ms |
コンパイル使用メモリ | 187,636 KB |
実行使用メモリ | 41,888 KB |
最終ジャッジ日時 | 2024-07-26 19:17:42 |
合計ジャッジ時間 | 19,977 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>// #include<atcoder/all>using namespace std;// using namespace atcoder;using ll = long long;using ull = unsigned long long;using P = pair<int,int>;#define rep(i,n) for(ll i = 0;i < (ll)n;i++)#define ALL(x) (x).begin(),(x).end()#define MOD 1000000007template<typename T>class Segtree{public:using F = function<T(T,T)>;int n;F f;T ti;vector<T> dat;Segtree(){};Segtree(F f,T ti): f(f),ti(ti){}void init(int N){n = 1;while(n < N)n <<= 1;dat.assign(n << 1,ti);}void build(const vector<T> &v){int N = v.size();init(N);rep(i,N)dat[n+i] = v[i];for(int i = n-1;i >= 0;i--)dat[i] = f(dat[(i << 1)|0],dat[(i << 1)|1]);}void set(int k,T x){dat[k+=n] = x;while(k >>= 1){dat[k] = f(dat[(k << 1)|0],dat[(k << 1)|1]);}}T get(int l,int r){T vl = ti,vr = ti;for(l += n,r += n;l < r;l >>= 1,r >>= 1){if(l & 1)vl = f(vl,dat[l++]);if(r & 1)vr = f(dat[--r],vr);}return f(vl,vr);}};const int mod = 998244353;int main(){int n;cin >> n;vector<int> v(n);vector<int> w(n);rep(i,n)cin >> v[i],w[i] = v[i];sort(ALL(w));w.erase(unique(ALL(w)),w.end());map<int,int> mp;int m = w.size();rep(i,m)mp[w[i]] = i;auto f = [&](pair<ll,ll> a,pair<ll,ll> b){return pair<ll,ll>{(a.first+b.first)%mod,(a.second+b.second)%mod};};Segtree<pair<ll,ll>> one(f,{0,0}),two(f,{0,0}),three(f,{0,0});one.build(vector<pair<ll,ll>>(m,{0,0}));two.build(vector<pair<ll,ll>>(m,{0,0}));three.build(vector<pair<ll,ll>>(m,{0,0}));rep(i,n){int k = mp[v[i]];{pair<ll,ll> x = one.get(k,k+1);x.first += v[i];x.second++;x.first %= mod;one.set(k,x);}{pair<ll,ll> x = two.get(k,k+1);pair<ll,ll> y = one.get(k+1,m);two.set(k,{(x.first+y.first+y.second*v[i]%mod)%mod,(x.second+y.second)%mod});}{pair<ll,ll> x = three.get(k,k+1);pair<ll,ll> y = two.get(k+1,m);three.set(k,{(x.first+y.first+y.second*v[i]%mod)%mod,(x.second+y.second)%mod});}}cout << three.get(0,m).first << "\n";return 0;}