結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-28 14:27:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,043 ms / 2,000 ms |
コード長 | 1,999 bytes |
コンパイル時間 | 1,996 ms |
コンパイル使用メモリ | 184,388 KB |
実行使用メモリ | 39,296 KB |
最終ジャッジ日時 | 2024-09-12 22:26:38 |
合計ジャッジ時間 | 25,508 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>using namespace std;//#define int long long#define REP(i,m,n) for(int i=(m);i<(n);i++)#define rep(i,n) REP(i,0,n)#define pb push_back#define all(a) a.begin(),a.end()#define rall(c) (c).rbegin(),(c).rend()#define mp make_pair#define endl '\n'#define vec vector<ll>#define mat vector<vector<ll> >#define fi first#define se secondtypedef long long ll;typedef unsigned long long ull;typedef pair<ll,ll> pll;typedef long double ld;typedef complex<double> comp;const ll INF=1e9+7;const ll inf=INF*INF;const ll MOD=998244353;const ll mod=MOD;const ll MAX=200010;const double PI=acos(-1.0);//BIT閉区間template< class T >struct BIT{vector< T > data;BIT(int sz){data.assign(++sz, 0);}T sum(int k){T ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return (ret);}void add(int k, T x){for(++k; k < data.size(); k += k & -k) data[k] += x;}};signed main(){ll n;cin>>n;vector<ll>a(n);set<ll>st;rep(i,n){cin>>a[i];st.insert(a[i]);}ll now=0;map<ll,ll>idx;for(auto e:st){idx[e]=now;now++;}BIT<ll>bit(now);BIT<ll>bit1(now);BIT<ll>bit2(now);BIT<ll>bit3(now);ll ans=0;vector<ll>cntl(n),cntr(n),suml(n),sumr(n);rep(i,n){cntl[i]=bit.sum(now-1)-bit.sum(idx[a[i]]);bit.add(idx[a[i]],1);}for(int i=n-1;i>=0;i--){if(idx[a[i]]>0)cntr[i]=bit1.sum(idx[a[i]]-1);bit1.add(idx[a[i]],1);}rep(i,n){suml[i]=bit2.sum(now-1)-bit2.sum(idx[a[i]]);suml[i]%=mod;bit2.add(idx[a[i]],a[i]);}for(int i=n-1;i>=0;i--){if(idx[a[i]]>0)sumr[i]=bit3.sum(idx[a[i]]-1);sumr[i]%=mod;bit3.add(idx[a[i]],a[i]);}rep(i,n){ans=(ans+a[i]%mod*cntl[i]%mod*cntr[i]%mod)%mod;ans=(ans+suml[i]*cntr[i]%mod)%mod;ans=(ans+sumr[i]*cntl[i]%mod)%mod;}cout<<ans<<endl;}