結果

問題 No.1300 Sum of Inversions
ユーザー Izayoi_R_sakuraIzayoi_R_sakura
提出日時 2020-11-27 22:19:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,174 ms / 2,000 ms
コード長 4,658 bytes
コンパイル時間 1,886 ms
コンパイル使用メモリ 150,040 KB
実行使用メモリ 39,928 KB
最終ジャッジ日時 2024-07-26 13:20:31
合計ジャッジ時間 28,429 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 882 ms
35,312 KB
testcase_04 AC 836 ms
34,888 KB
testcase_05 AC 642 ms
24,064 KB
testcase_06 AC 993 ms
37,160 KB
testcase_07 AC 946 ms
36,376 KB
testcase_08 AC 1,060 ms
38,224 KB
testcase_09 AC 1,030 ms
38,044 KB
testcase_10 AC 507 ms
21,888 KB
testcase_11 AC 525 ms
22,016 KB
testcase_12 AC 866 ms
34,972 KB
testcase_13 AC 820 ms
34,668 KB
testcase_14 AC 1,174 ms
39,628 KB
testcase_15 AC 1,031 ms
37,952 KB
testcase_16 AC 906 ms
35,704 KB
testcase_17 AC 497 ms
21,632 KB
testcase_18 AC 584 ms
23,168 KB
testcase_19 AC 702 ms
33,272 KB
testcase_20 AC 741 ms
33,520 KB
testcase_21 AC 723 ms
33,640 KB
testcase_22 AC 622 ms
24,064 KB
testcase_23 AC 983 ms
37,156 KB
testcase_24 AC 655 ms
24,448 KB
testcase_25 AC 541 ms
22,656 KB
testcase_26 AC 531 ms
22,656 KB
testcase_27 AC 613 ms
23,808 KB
testcase_28 AC 1,071 ms
38,532 KB
testcase_29 AC 740 ms
33,540 KB
testcase_30 AC 1,039 ms
38,028 KB
testcase_31 AC 656 ms
24,192 KB
testcase_32 AC 664 ms
24,576 KB
testcase_33 AC 54 ms
11,008 KB
testcase_34 AC 110 ms
11,008 KB
testcase_35 AC 582 ms
39,896 KB
testcase_36 AC 604 ms
39,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <math.h>
#include <random>
#include <chrono>
using namespace std ;
using ll = long long ;
using ld = long double ;
template<class T> using V = vector<T> ;
template<class T> using VV = V<V<T>> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 998244353 ;
long double pie = acos(-1) ;
ll INF = 1000000000000 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
void fix_cout(){cout << fixed << setprecision(20) ;}
template<class T> void chmax(T &a,T &b){if(a<b) a = b ;}
template<class T> void chmin(T &a,T &b){if(a>b) a = b ;}

template<class T>
class SGT{
    public :
    int n ;
    vector<T> num ;
    function<T(T,T)> f ;
    T d ;

    // コンストラクタ：サイズ、関数、単位元を指定
    SGT(size_t n_,function<T(T,T)> f_,T d_) : f(f_),d(d_){
        n = 1 ;
        while(n<n_) n *= 2 ;
        num = vector<T>(2*n-1,d) ;
    }

    // sz個のaで前から初期化
    void init(int sz,T a){
        for(int i=0;i<sz;i++) num[i+n-1] = a ;
        for(int i=n-2;i>=0;i--) num[i] = f(num[i*2+1],num[i*2+1]) ;
    }

    // 配列aで前から初期化
    void init(vector<T> &a){
        for(int i=0;i<a.size();i++) num[i+n-1] = a[i] ;
        for(int i=n-2;i>=0;i--) num[i] = f(num[i*2+1],num[i*2+2]) ;
    }

    // 0-indexedでp番目をaで上書き
    void update(int p,T a){
        p += n-1 ;
        num[p] = a ;
        while(p){
            p = (p-1)/2 ;
            num[p] = f(num[p*2+1],num[p*2+2]) ;
        }
    }

    // 0-indexedでp番目にaを加算
    void add(int p,T a){
        p += n-1 ;
        num[p] += a ;
        while(p){
            p = (p-1)/2 ;
            num[p] = f(num[p*2+1],num[p*2+2]) ;
        }        
    }
    
    T query(int a,int b,int cur=0,int l=0,int r=-1){
        if(r<0) r = n ;
        if(r<=a||b<=l) return d ;
        if(a<=l&&r<=b) return num[cur] ;
        T r1 = query(a,b,cur*2+1,l,(l+r)/2) ;
        T r2 = query(a,b,cur*2+2,(l+r)/2,r) ;
        return f(r1,r2) ;
    }

    T operator[](int p){
        return num[p+n-1] ;
    }

    int bsr(int a,int b,T x,function<bool(T,T)> check,int l=0,int r=-1,int cur=0){
        if(r<0) r = n ;
        cout << l << " " << r << " " << cur << endl ;
        if(!check(num[cur],x)||r<=a||b<=l) return a-1 ;
        if(cur>=n-1) return cur-(n-1) ;
        int right = bsr(a,b,x,check,(l+r)/2,r,cur*2+2) ;
        if(right==a-1){
            return bsr(a,b,x,check,l,(l+r)/2,cur*2+1) ;
        }else{
            return right ;
        }
    }

    int bsl(int a,int b,T x,function<bool(T,T)> check,int l=0,int r=-1,int cur=0){
        if(r<0) r = n ;
        if(!check(num[cur],x)||r<=a||b<=l) return b ;
        if(cur>=n-1) return cur-(n-1) ;
        int left = bsl(a,b,x,check,l,(l+r)/2,cur*2+1) ;
        if(left==b){
            return bsl(a,b,x,check,(l+r)/2,r,cur*2+2) ;
        }else{
            return left ;
        }
    }
} ;

int main(){
	int n ; cin >> n ;
	V<ll> a(n) ;
	map<ll,int> pos ;
	for(int i=0;i<n;i++){
		cin >> a[i] ;
		pos[a[i]]++ ;
	}
	int  cnt = 0 ;
	for(auto &p:pos){
		p.second = cnt ;
		cnt++ ;
	}
	// for(auto p:pos){
	// 	cout << p.first << " " << p.second << endl ;
	// }
	SGT<ll> mx(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> mn(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> s1(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> s2(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	V<ll> cnt1(n,0),cnt2(n,0),cnt3(n,0),cnt4(n,0) ;
	for(int i=0;i<n;i++){
		cnt1[i] = mx.query(pos[a[i]]+1,mx.n) ;
		mx.add(pos[a[i]],1) ;
	}
	for(int i=n-1;i>=0;i--){
		cnt2[i] = mn.query(0,pos[a[i]]) ;
		mn.add(pos[a[i]],1) ;
	}
	for(int i=0;i<n;i++){
		cnt3[i] = s1.query(pos[a[i]]+1,s1.n) ;
		s1.add(pos[a[i]],cnt1[i]) ;
	}
	for(int i=n-1;i>=0;i--){
		cnt4[i] = s2.query(0,pos[a[i]]) ;
		s2.add(pos[a[i]],cnt2[i]) ;
	}
	ll ans = 0 ;
	for(int i=0;i<n;i++){
		ans += a[i]%mod*((cnt1[i]*cnt2[i]%mod+cnt3[i]+cnt4[i])%mod)%mod ;
		ans %= mod ;
		// cout << ans << endl ;
	}
	cout << ans << endl ;
	// for(auto i:cnt1) cout << i << " " ; cout << endl ;
	// for(auto i:cnt2) cout << i << " " ; cout << endl ;
	// for(auto i:cnt3) cout << i << " " ; cout << endl ;
	// for(auto i:cnt4) cout << i << " " ; cout << endl ;
}
0