結果
問題 | No.1300 Sum of Inversions |
ユーザー | kappybar |
提出日時 | 2020-11-27 22:06:11 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 3,807 bytes |
コンパイル時間 | 2,151 ms |
コンパイル使用メモリ | 174,652 KB |
実行使用メモリ | 15,632 KB |
最終ジャッジ日時 | 2023-10-01 06:03:00 |
合計ジャッジ時間 | 7,796 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 130 ms
12,876 KB |
testcase_04 | AC | 129 ms
12,152 KB |
testcase_05 | AC | 102 ms
10,880 KB |
testcase_06 | AC | 147 ms
13,792 KB |
testcase_07 | AC | 140 ms
13,344 KB |
testcase_08 | AC | 157 ms
14,320 KB |
testcase_09 | AC | 155 ms
14,500 KB |
testcase_10 | AC | 84 ms
9,556 KB |
testcase_11 | AC | 85 ms
9,596 KB |
testcase_12 | AC | 128 ms
12,480 KB |
testcase_13 | AC | 124 ms
12,348 KB |
testcase_14 | AC | 170 ms
15,444 KB |
testcase_15 | AC | 153 ms
14,360 KB |
testcase_16 | AC | 132 ms
12,760 KB |
testcase_17 | AC | 82 ms
9,248 KB |
testcase_18 | AC | 94 ms
10,044 KB |
testcase_19 | AC | 113 ms
11,540 KB |
testcase_20 | AC | 115 ms
11,672 KB |
testcase_21 | AC | 114 ms
11,592 KB |
testcase_22 | AC | 102 ms
10,876 KB |
testcase_23 | AC | 148 ms
13,800 KB |
testcase_24 | AC | 106 ms
10,968 KB |
testcase_25 | AC | 90 ms
9,972 KB |
testcase_26 | AC | 89 ms
9,860 KB |
testcase_27 | AC | 99 ms
10,572 KB |
testcase_28 | AC | 160 ms
14,724 KB |
testcase_29 | AC | 114 ms
11,548 KB |
testcase_30 | AC | 155 ms
14,400 KB |
testcase_31 | AC | 103 ms
10,956 KB |
testcase_32 | AC | 107 ms
11,160 KB |
testcase_33 | AC | 77 ms
15,516 KB |
testcase_34 | AC | 129 ms
15,632 KB |
testcase_35 | AC | 103 ms
15,448 KB |
testcase_36 | AC | 123 ms
15,460 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define chmin(x,y) x = min((x),(y)); #define chmax(x,y) x = max((x),(y)); using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; const int INF = 1e9; const long long LINF = 1e17; //const int MOD = 1000000007; const int MOD = 998244353; const double PI = 3.14159265358979323846; template<int mod> struct ModInt{ long long x=0; constexpr ModInt(long long x=0):x((x%mod+mod)%mod){} constexpr ModInt operator+(const ModInt& r)const{return ModInt(*this)+=r;} constexpr ModInt operator-(const ModInt& r)const{return ModInt(*this)-=r;} constexpr ModInt operator*(const ModInt& r)const{return ModInt(*this)*=r;} constexpr ModInt operator/(const ModInt& r)const{return ModInt(*this)/=r;} constexpr ModInt& operator+=(const ModInt& r){ if((x+=r.x)>=mod) x-=mod; return *this;} constexpr ModInt& operator-=(const ModInt& r){ if((x-=r.x)<0) x+=mod; return *this;} constexpr ModInt& operator*=(const ModInt& r){ if((x*=r.x)>=mod) x%=mod; return *this;} constexpr ModInt& operator/=(const ModInt& r){ return *this*=r.inv();} ModInt inv() const { long long s=x,sx=1,sy=0,t=mod,tx=0,ty=1; while(s%t!=0){ long long temp=s/t,u=s-t*temp,ux=sx-temp*tx,uy=sy-temp*ty; s=t;sx=tx;sy=ty; t=u;tx=ux;ty=uy; } return ModInt(tx); } ModInt pow(long long n) const { ModInt a=1; ModInt b=*this; while(n>0){ if(n&1) a*=b; b*=b; n>>=1; } return a; } friend constexpr ostream& operator<<(ostream& os,const ModInt<mod>& a) {return os << a.x;} friend constexpr istream& operator>>(istream& is,ModInt<mod>& a) {return is >> a.x;} }; using mint = ModInt<MOD>; //1-indexedに注意!!! struct BIT{ private: int n,n_; vector<long long> bit; public: BIT(int n):n(n){ bit.resize(n+1); n_ = 1; while(n_<=n) n_<<=1; n_ >>= 1; } //1-index long long sum(int i){ long long res = 0; while(i > 0){ res += bit[i]; i -= i&-i; } return res; } //1-index void add(int i,long long val){ while(i <= n){ bit[i] += val; i += i&-i; } } //return 1-index int lowerbound(long long w){ if(w <= 0) return 0; int x = 0; for(int k=n_;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<w){ w -= bit[x+k]; x += k; } } return x+1; } }; template<typename T> vector<T> compress(vector<T> &a){ vector<T> val = a; int n = (int)a.size(); sort(val.begin(),val.end()); val.erase(unique(val.begin(),val.end()),val.end()); for(int i=0;i<n;i++){ a[i] = lower_bound(val.begin(),val.end(),a[i]) - val.begin(); } return val; } int main(){ int n; cin >> n; vector<ll> a(n); vector<ll> b(n),c(n); rep(i,n) cin >> a[i]; vector<ll> mp = compress(a); BIT bit(n); rep(i,n){ b[i] = i - bit.sum(a[i]+1); bit.add(a[i]+1,1); } BIT bb(n); rep(i,n){ c[n-i-1] = bb.sum(a[n-i-1]-1+1); bb.add(a[n-i-1]+1,1); } mint ans = 0; rep(i,n){ ans += mint(b[i]) * mint(c[i]) * mint(mp[a[i]]); } BIT bitsum(n); mint cum = 0; rep(i,n){ ans += mint(c[i]) * (cum - mint(bitsum.sum(a[i]+1))); bitsum.add(a[i]+1,mp[a[i]]); cum += mp[a[i]]; } BIT bbsum(n); rep(i,n){ ans += mint(b[n-1-i]) * mint(bbsum.sum(a[n-i-1]-1+1)); bbsum.add(a[n-i-1]+1,mp[a[n-i-1]]); } cout << ans << endl; return 0; }