結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 22:02:04 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 176 ms / 2,000 ms |
コード長 | 2,042 bytes |
コンパイル時間 | 1,106 ms |
コンパイル使用メモリ | 91,024 KB |
実行使用メモリ | 15,856 KB |
最終ジャッジ日時 | 2024-07-26 12:45:47 |
合計ジャッジ時間 | 7,366 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#include <complex>#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define all(x) (x).begin(),(x).end()#define inf 1e18#define mod 998244353using namespace std;typedef long long llint;typedef long long ll;typedef pair<llint, llint> P;struct BIT{int size;vector<llint> bit;BIT(){size = 0;}BIT(int s){size = s;bit.resize(size+1);init();}void init(){for(int i = 1; i <= size; i++) bit[i] = 0;}llint query(int i){llint ret = 0;while(i > 0){ret += bit[i], ret %= mod;i -= i&(-i);}return ret;}void add(int i, llint x){while(i <= size){bit[i] += x, bit[i] %= mod;i += i&(-i);}}};ll n;ll a[200005];vector<ll> comp;ll lnum[200005], lsum[200005];ll rnum[200005], rsum[200005];BIT bit(200005), bit2(200005);int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;rep(i, 1, n){cin >> a[i];comp.push_back(a[i]);}sort(all(comp));comp.erase(unique(all(comp)), comp.end());rep(i, 1, n) a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;rep(i, 1, n){lnum[i] = bit.query(n) - bit.query(a[i]);lsum[i] = bit2.query(n) - bit2.query(a[i]) + mod, lsum[i] %= mod;bit.add(a[i], 1), bit2.add(a[i], comp[a[i]-1]);}bit.init(), bit2.init();for(int i = n; i >= 1; i--){rnum[i] = bit.query(a[i]-1);rsum[i] = bit2.query(a[i]-1) + mod, rsum[i] %= mod;bit.add(a[i], 1), bit2.add(a[i], comp[a[i]-1]);}ll ans = 0;rep(j, 1, n){ans += comp[a[j]-1] * lnum[j] % mod * rnum[j] % mod, ans %= mod;ans += lsum[j] * rnum[j] % mod, ans %= mod;ans += rsum[j] * lnum[j] % mod, ans %= mod;}cout << ans << endl;return 0;}