結果
問題 | No.1300 Sum of Inversions |
ユーザー | persimmon-persimmon |
提出日時 | 2021-06-29 10:35:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,049 ms / 2,000 ms |
コード長 | 1,977 bytes |
コンパイル時間 | 307 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 174,956 KB |
最終ジャッジ日時 | 2024-06-25 17:28:18 |
合計ジャッジ時間 | 25,782 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
52,864 KB |
testcase_01 | AC | 38 ms
52,352 KB |
testcase_02 | AC | 39 ms
52,352 KB |
testcase_03 | AC | 730 ms
129,664 KB |
testcase_04 | AC | 755 ms
129,792 KB |
testcase_05 | AC | 594 ms
127,644 KB |
testcase_06 | AC | 825 ms
141,656 KB |
testcase_07 | AC | 850 ms
134,016 KB |
testcase_08 | AC | 890 ms
146,068 KB |
testcase_09 | AC | 913 ms
145,796 KB |
testcase_10 | AC | 556 ms
131,768 KB |
testcase_11 | AC | 509 ms
131,968 KB |
testcase_12 | AC | 782 ms
129,024 KB |
testcase_13 | AC | 781 ms
128,640 KB |
testcase_14 | AC | 1,049 ms
174,956 KB |
testcase_15 | AC | 921 ms
146,076 KB |
testcase_16 | AC | 823 ms
129,948 KB |
testcase_17 | AC | 486 ms
126,080 KB |
testcase_18 | AC | 552 ms
132,756 KB |
testcase_19 | AC | 649 ms
124,364 KB |
testcase_20 | AC | 664 ms
124,160 KB |
testcase_21 | AC | 654 ms
124,736 KB |
testcase_22 | AC | 614 ms
128,776 KB |
testcase_23 | AC | 827 ms
140,708 KB |
testcase_24 | AC | 683 ms
125,696 KB |
testcase_25 | AC | 587 ms
132,608 KB |
testcase_26 | AC | 521 ms
132,048 KB |
testcase_27 | AC | 654 ms
133,120 KB |
testcase_28 | AC | 1,000 ms
152,808 KB |
testcase_29 | AC | 711 ms
124,876 KB |
testcase_30 | AC | 977 ms
146,672 KB |
testcase_31 | AC | 600 ms
128,640 KB |
testcase_32 | AC | 660 ms
126,080 KB |
testcase_33 | AC | 355 ms
123,600 KB |
testcase_34 | AC | 370 ms
135,100 KB |
testcase_35 | AC | 419 ms
143,660 KB |
testcase_36 | AC | 449 ms
173,936 KB |
ソースコード
def main0(n,a): mod=10**9+7 ans=0 for i in range(n-2): for j in range(i+1,n-1): if a[i]<=a[j]:continue for k in range(j+1,n): if a[i]>a[j]>a[k]: ans+=a[i]+a[j]+a[k] ans%=mod return ans # 0-indexed binary indexed tree class BIT: def __init__(self, n): self.n = n self.data = [0]*(n+1) self.el = [0]*(n+1) # sum of [0,i) sum(a[:i]) def sum(self, i): if i==0:return 0 s = 0 while i > 0: s += self.data[i] i -= i & -i return s def add(self, i, x): i+=1 self.el[i] += x while i <= self.n: self.data[i] += x i += i & -i # sum of [l,r) sum(a[l:r]) def sumlr(self, i, j): return self.sum(j) - self.sum(i) # a[i] def get(self,i): i+=1 return self.el[i] def main1(n,a): mod=998244353 # あるiについてj<iでa[j]>a[i]のものとその逆のものを調べる。 # 合計と個数がわかればOK ary0=[0]*n # ary0[i]:j<iでa[j]>a[i]となるものの個数 ary1=[0]*n # ary0[i]:i<jでa[i]>a[j]となるものの個数 pa=list(set(a)) pa.sort() ap={x:i for i,x in enumerate(pa)} bit=BIT(n) for i in range(n): ary0[i]=i-bit.sum(ap[a[i]]+1) bit.add(ap[a[i]],1) bit=BIT(n) for i in reversed(range(n)): ary1[i]=bit.sum(ap[a[i]]) bit.add(ap[a[i]],1) sary0=[0]*n # ary0[i]:j<iでa[j]>a[i]となるものの総和 sary1=[0]*n # ary0[i]:i<jでa[i]>a[j]となるものの総和 aa=[[i,x] for i,x in enumerate(a)] aa.sort(key=lambda x:x[1]) bit=BIT(n) for i,x in aa[::-1]: sary0[i]=bit.sum(i) bit.add(i,x) bit=BIT(n) tmp=0 for i,x in aa: sary1[i]=tmp-bit.sum(i) bit.add(i,x) tmp+=x ans=0 for i in range(n): ans+=ary0[i]*sary1[i] ans+=ary1[i]*sary0[i] ans+=ary0[i]*ary1[i]*a[i] ans%=mod return ans if __name__=='__main__': n=int(input()) a=list(map(int,input().split())) #ret0=main0(n,a) #print(ret0) ret1=main1(n,a) print(ret1)