結果

問題 No.1975 Zigzag Sequence
コンテスト
ユーザー prussian_coder
提出日時 2022-06-10 22:57:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 331 ms / 2,000 ms
コード長 1,199 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 134,016 KB
最終ジャッジ日時 2024-09-21 06:44:43
合計ジャッジ時間 8,272 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)
    self.depth = n.bit_length()
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s
  
  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

  def lower_bound(self, x):
  #xを超えない最大のiを返す
    sum_ = 0
    pos = 0
    for i in range(self.depth, -1, -1):
      k = pos + (1 << i)
      if k <= self.size and sum_ + self.tree[k] < x:
        sum_ += self.tree[k]
        pos += 1 << i
    return pos + 1, sum_
    
    
N=int(input())
A=[int(x) for x in input().split()]
D={j:i for i,j in enumerate(sorted(set(A)))}
E={i:j for i,j in enumerate(sorted(set(A)))}
M=len(D)

left_up=[0]*N
left_down=[0]*N
right_up=[0]*N
right_down=[0]*N
L=Bit(M)
R=Bit(M)
l=1
mod=10**9+7

for i in range(N):
	left_down[i]=L.sum(D[A[i]])
	left_up[i]=L.sum(M)-L.sum(D[A[i]]+1)
	L.add(D[A[i]]+1,l)
	l=l*2%mod
r=1

for i in range(N):
	j=-i-1
	right_down[j]=R.sum(D[A[j]])
	right_up[j]=R.sum(M)-R.sum(D[A[j]]+1)
	R.add(D[A[j]]+1,r)
	r=r*2%mod
print(sum([(left_up[i]*right_up[i]+left_down[i]*right_down[i])%mod for i in range(N)])%mod)
0