#585543 (C++17) No.1300 Sum of Inversions

提出ソース

結果

問題	No.1300 Sum of Inversions
ユーザー	Izayoi_R_sakura
提出日時	2020-11-27 22:13:55
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,664 bytes
コンパイル時間	1,816 ms
コンパイル使用メモリ	151,044 KB
実行使用メモリ	32,000 KB
最終ジャッジ日時	2024-07-26 13:09:27
合計ジャッジ時間	26,871 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	52 ms 11,008 KB
testcase_34	AC	108 ms 11,136 KB
testcase_35	WA	-
testcase_36	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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<int> mx(pos.size(),[](int a,int b){return a+b ;},0) ;
	SGT<int> mn(pos.size(),[](int a,int b){return a+b ;},0) ;
	SGT<int> s1(pos.size(),[](int a,int b){return a+b ;},0) ;
	SGT<int> s2(pos.size(),[](int a,int 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 ;
		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 ;
}

yukicoder

結果

テストケース

ソースコード