結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:26:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,187 bytes |
コンパイル時間 | 119 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 63,796 KB |
最終ジャッジ日時 | 2024-09-21 06:55:38 |
合計ジャッジ時間 | 36,649 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 10 TLE * 16 |
ソースコード
class BinaryIndexedTree:def __init__(self, n, mod):self.size = nself.tree = [0]*(n+1)self.mod = moddef add(self, i, x):while i <= self.size:self.tree[i] = (self.tree[i]+x)%self.modi += i&-idef sum(self, i):s = 0while i > 0:s = (s+self.tree[i])%self.modi -= i&-ireturn sn = int(input())a = list(map(int, input().split()))mod = 10**+7itov = sorted(set(a))vtoi = {v: i for i, v in enumerate(itov)}b = [vtoi[v]+1 for v in a]r = [pow(2, i, mod) for i in range(n)]ldans = [0]*nluans = [0]*nldbit = BinaryIndexedTree(n, mod)lubit = BinaryIndexedTree(n, mod)rdans = [0]*nruans = [0]*nrdbit = BinaryIndexedTree(n, mod)rubit = BinaryIndexedTree(n, mod)ans = 0for i, v in enumerate(b):ldans[i] = ldbit.sum(v-1)luans[i] = lubit.sum(n-v)ldbit.add(v, r[i])lubit.add(n+1-v, r[i])for i, v in enumerate(b[::-1]):rdans[i] = rdbit.sum(v-1)ruans[i] = rubit.sum(n-v)rdbit.add(v, r[i])rubit.add(n+1-v, r[i])for i in range(n):ans = (ans+ldans[i]*rdans[n-1-i])%modans = (ans+luans[i]*ruans[n-1-i])%modprint(ans)