結果

問題 No.1300 Sum of Inversions
ユーザー SSRS
提出日時 2020-11-27 21:34:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 303 ms / 2,000 ms
コード長 1,672 bytes
コンパイル時間 2,027 ms
コンパイル使用メモリ 183,344 KB
実行使用メモリ 26,624 KB
最終ジャッジ日時 2024-07-26 11:49:25
合計ジャッジ時間 10,172 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
struct binary_indexed_tree{
int N;
vector<long long> BIT;
binary_indexed_tree(int N): N(N){
BIT = vector<long long>(N + 1, 0);
}
void add(int i, long long x){
i++;
while (i <= N){
BIT[i] += x;
BIT[i] %= MOD;
i += i & -i;
}
}
long long sum(int i){
long long ans = 0;
while (i > 0){
ans += BIT[i];
ans %= MOD;
i -= i & -i;
}
return ans;
}
long long sum(int L, int R){
return (sum(R) - sum(L) + MOD) % MOD;
}
};
int main(){
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++){
cin >> A[i];
}
vector<int> A2 = A;
sort(A2.begin(), A2.end());
A2.erase(unique(A2.begin(), A2.end()), A2.end());
int cnt = A2.size();
map<int, int> mp;
for (int i = 0; i < cnt; i++){
mp[A2[i]] = i;
}
for (int i = 0; i < N; i++){
A[i] = mp[A[i]];
}
vector<long long> F(N, 0);
vector<long long> Fc(N, 0);
binary_indexed_tree BIT1(cnt);
binary_indexed_tree BIT2(cnt);
for (int i = 0; i < N; i++){
F[i] = BIT1.sum(A[i] + 1, cnt);
Fc[i] = BIT2.sum(A[i] + 1, cnt);
BIT1.add(A[i], A2[A[i]]);
BIT2.add(A[i], 1);
}
vector<long long> B(N, 0);
vector<long long> Bc(N, 0);
binary_indexed_tree BIT3(cnt);
binary_indexed_tree BIT4(cnt);
for (int i = N - 1; i >= 0; i--){
B[i] = BIT3.sum(A[i]);
Bc[i] = BIT4.sum(A[i]);
BIT3.add(A[i], A2[A[i]]);
BIT4.add(A[i], 1);
}
long long ans = 0;
for (int i = 0; i < N; i++){
ans += F[i] * Bc[i] + B[i] * Fc[i] + Bc[i] * Fc[i] % MOD * A2[A[i]];
ans %= MOD;
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0