結果

問題 No.1300 Sum of Inversions
ユーザー ok
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0