結果
| 問題 | No.1300 Sum of Inversions |
| ユーザー |
 kenta255
|
| 提出日時 | 2020-11-27 22:33:36 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,190 ms / 2,000 ms |
| コード長 | 3,074 bytes |
| コンパイル時間 | 3,691 ms |
| コンパイル使用メモリ | 222,736 KB |
| 実行使用メモリ | 36,608 KB |
| 最終ジャッジ日時 | 2023-10-09 20:36:57 |
| 合計ジャッジ時間 | 33,294 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 889 ms
32,672 KB |
| testcase_04 | AC | 859 ms
32,228 KB |
| testcase_05 | AC | 655 ms
22,196 KB |
| testcase_06 | AC | 973 ms
34,260 KB |
| testcase_07 | AC | 1,058 ms
33,700 KB |
| testcase_08 | AC | 1,190 ms
34,872 KB |
| testcase_09 | AC | 1,179 ms
34,912 KB |
| testcase_10 | AC | 590 ms
20,148 KB |
| testcase_11 | AC | 574 ms
20,092 KB |
| testcase_12 | AC | 881 ms
32,472 KB |
| testcase_13 | AC | 828 ms
32,096 KB |
| testcase_14 | AC | 1,132 ms
36,444 KB |
| testcase_15 | AC | 1,043 ms
34,872 KB |
| testcase_16 | AC | 861 ms
33,196 KB |
| testcase_17 | AC | 540 ms
19,836 KB |
| testcase_18 | AC | 587 ms
20,884 KB |
| testcase_19 | AC | 749 ms
30,972 KB |
| testcase_20 | AC | 743 ms
31,236 KB |
| testcase_21 | AC | 722 ms
31,288 KB |
| testcase_22 | AC | 643 ms
22,092 KB |
| testcase_23 | AC | 959 ms
34,232 KB |
| testcase_24 | AC | 730 ms
22,268 KB |
| testcase_25 | AC | 587 ms
20,620 KB |
| testcase_26 | AC | 569 ms
20,744 KB |
| testcase_27 | AC | 644 ms
21,536 KB |
| testcase_28 | AC | 1,068 ms
35,464 KB |
| testcase_29 | AC | 780 ms
30,900 KB |
| testcase_30 | AC | 1,020 ms
34,956 KB |
| testcase_31 | AC | 645 ms
22,052 KB |
| testcase_32 | AC | 708 ms
22,384 KB |
| testcase_33 | AC | 677 ms
24,016 KB |
| testcase_34 | AC | 733 ms
24,032 KB |
| testcase_35 | AC | 830 ms
36,608 KB |
| testcase_36 | AC | 852 ms
36,512 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v)) //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
#define num_l(a,v) POSL(a,v) //v未満の要素数
#define num_eql(a,v) POSU(a,v) //v以下の要素数
#define num_h(a,v) (a.size() - POSU(a,v)) //vより大きい要素数
#define num_eqh(a,v) (a.size() - POSL(a,v)) //v以上の要素数
template <typename T>
class Seg_Tree{
public: // 0-index
vector<T> dat;
T initial,M;
int n;
T unite(T a,T b){//
return ( a + b ) % M;
}
Seg_Tree(int n0_=1,T initial_=1,T M_=1){
initsize(n0_,initial_,M_);
}
void initsize(int n0,T initial_,T M_){
M = M_;
initial = initial_;
int k=1;
while(1){
if(n0<=k){
n=k;
dat.resize(2*n-1);
for(int i=0;i<2*n-1;i++)dat[i]=initial;
break;
}
k*=2;
}
}
//i banme wo x nisuru
void update(int i,T x){
i += n-1;
dat[i] = x;
while(i>0){
i = (i-1) / 2;
dat[i] = unite(dat[i*2+1],dat[i*2+2]);
}
}
//[a,b)
T query0(int a,int b,int k,int l,int r){
if(r<=a || b<=l)return initial;
if(a<=l && r<=b)return dat[k];
else{
T vl = query0(a,b,k*2+1,l,(l+r)/2);
T vr = query0(a,b,k*2+2,(l+r)/2,r);
return unite(vl,vr);
}
}
//return [a,b)
T query(int a,int b){
return query0(a,b,0,0,n);
}
};
int main(){
ll N;
cin >> N;
vector<ll> A(N);
vector<P> B(N);
FOR(i,0,N){
cin >> A[i];
B[i] = {A[i],i};
}
SORT(B);
ll mod = 998244353;
Seg_Tree<ll> sum0(N,0,mod),num0(N,0,mod);//small
Seg_Tree<ll> sum1(N,0,mod),num1(N,0,mod);//big
map<ll,ll> count;
FOR(i,0,N){
sum1.update(i,A[i]);
num1.update(i,1);
count[A[i]]++;
}
ll ans = 0;
FOR(i,0,N){
int k = count[ B[i].first ];
FOR(j,i,i+k){
sum1.update(B[j].second , 0);
num1.update(B[j].second , 0);
}
FOR(j,i,i+k){
ll num1_ = num1.query(0,B[j].second);
ll num0_ = num0.query(B[j].second+1,N+1);
( ans += (B[j].first * num1_ % mod * num0_) % mod ) %= mod;
( ans += (sum1.query(0,B[j].second) * num0_) % mod ) %= mod;//右
( ans += (sum0.query(B[j].second+1,N) * num1_) % mod ) %= mod;//左
}
FOR(j,i,i+k){
sum0.update(B[j].second , B[j].first);
num0.update(B[j].second , 1);
}
count[B[i].first] = 0;
i += k-1;
}
cout << ans << endl;
}