結果
問題 | No.1300 Sum of Inversions |
ユーザー | publfl |
提出日時 | 2020-11-27 21:56:39 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,141 ms / 2,000 ms |
コード長 | 1,620 bytes |
コンパイル時間 | 976 ms |
コンパイル使用メモリ | 72,796 KB |
実行使用メモリ | 40,060 KB |
最終ジャッジ日時 | 2023-10-01 05:37:28 |
合計ジャッジ時間 | 28,449 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
9,336 KB |
testcase_01 | AC | 3 ms
9,344 KB |
testcase_02 | AC | 3 ms
9,344 KB |
testcase_03 | AC | 864 ms
27,640 KB |
testcase_04 | AC | 827 ms
26,664 KB |
testcase_05 | AC | 664 ms
22,552 KB |
testcase_06 | AC | 978 ms
30,324 KB |
testcase_07 | AC | 943 ms
29,128 KB |
testcase_08 | AC | 1,107 ms
32,008 KB |
testcase_09 | AC | 1,065 ms
31,752 KB |
testcase_10 | AC | 536 ms
19,332 KB |
testcase_11 | AC | 549 ms
19,612 KB |
testcase_12 | AC | 850 ms
27,088 KB |
testcase_13 | AC | 810 ms
26,460 KB |
testcase_14 | AC | 1,141 ms
34,224 KB |
testcase_15 | AC | 1,042 ms
31,372 KB |
testcase_16 | AC | 920 ms
28,132 KB |
testcase_17 | AC | 571 ms
18,772 KB |
testcase_18 | AC | 613 ms
21,212 KB |
testcase_19 | AC | 739 ms
24,192 KB |
testcase_20 | AC | 754 ms
24,788 KB |
testcase_21 | AC | 748 ms
24,568 KB |
testcase_22 | AC | 658 ms
22,660 KB |
testcase_23 | AC | 960 ms
30,404 KB |
testcase_24 | AC | 696 ms
23,500 KB |
testcase_25 | AC | 578 ms
20,404 KB |
testcase_26 | AC | 579 ms
20,188 KB |
testcase_27 | AC | 718 ms
22,044 KB |
testcase_28 | AC | 1,093 ms
32,508 KB |
testcase_29 | AC | 741 ms
24,504 KB |
testcase_30 | AC | 1,019 ms
31,732 KB |
testcase_31 | AC | 676 ms
22,888 KB |
testcase_32 | AC | 698 ms
23,408 KB |
testcase_33 | AC | 222 ms
6,164 KB |
testcase_34 | AC | 235 ms
6,176 KB |
testcase_35 | AC | 518 ms
40,060 KB |
testcase_36 | AC | 525 ms
40,044 KB |
ソースコード
#include <stdio.h> #include <vector> #include <algorithm> #include <map> #define MOD 998244353 struct segTree{ long long int value[800010]; void addValue(int ind, long long int val, int l=1, int r=200000, int v=1) { if(l==r) value[v] += val, value[v] %= MOD; else { int h = (l+r)/2; if(ind<=h) addValue(ind,val,l,h,2*v); else addValue(ind,val,h+1,r,2*v+1); value[v] = (value[2*v]+value[2*v+1])%MOD; } } long long int getValue(int L, int R, int l=1, int r=200000, int v=1) { if(L>R) return 0; if(L<=l&&r<=R) return value[v]; else if(r<L) return 0; else if(R<l) return 0; else { int h = (l+r)/2; long long int s1 = getValue(L,R,l,h,2*v); long long int s2 = getValue(L,R,h+1,r,2*v+1); return (s1+s2)%MOD; } } }T1,T2,T3,T4; long long int x[200010]; std::vector<long long int> index; std::map<long long int,int> hash; int main() { int a; scanf("%d",&a); for(int i=1;i<=a;i++) scanf("%d",&x[i]); for(int i=1;i<=a;i++) index.push_back(x[i]); std::sort(index.begin(),index.end()); index.erase(std::unique(index.begin(),index.end()),index.end()); for(int i=0;i<index.size();i++) hash[index[i]] = i+1; long long int ans = 0; for(int i=1;i<=a;i++) { long long int S3 = T3.getValue(hash[x[i]]+1,a); long long int S4 = T4.getValue(hash[x[i]]+1,a); ans += (S4+S3*x[i])%MOD; ans %= MOD; long long int S1 = T1.getValue(hash[x[i]]+1,a); long long int S2 = T2.getValue(hash[x[i]]+1,a); T3.addValue(hash[x[i]],S1); T4.addValue(hash[x[i]],(S2+S1*x[i])%MOD); T1.addValue(hash[x[i]],1); T2.addValue(hash[x[i]],x[i]); } printf("%lld",ans); }