結果

問題 No.1975 Zigzag Sequence
ユーザー prussian_coderprussian_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,736 KB
testcase_01 AC 38 ms
52,096 KB
testcase_02 AC 40 ms
52,736 KB
testcase_03 AC 91 ms
77,260 KB
testcase_04 AC 81 ms
77,048 KB
testcase_05 AC 237 ms
93,440 KB
testcase_06 AC 212 ms
98,860 KB
testcase_07 AC 92 ms
77,292 KB
testcase_08 AC 162 ms
84,736 KB
testcase_09 AC 294 ms
118,272 KB
testcase_10 AC 197 ms
92,776 KB
testcase_11 AC 218 ms
96,128 KB
testcase_12 AC 98 ms
77,696 KB
testcase_13 AC 39 ms
52,224 KB
testcase_14 AC 38 ms
52,608 KB
testcase_15 AC 39 ms
52,352 KB
testcase_16 AC 40 ms
52,224 KB
testcase_17 AC 39 ms
52,608 KB
testcase_18 AC 166 ms
88,448 KB
testcase_19 AC 154 ms
88,448 KB
testcase_20 AC 203 ms
90,784 KB
testcase_21 AC 205 ms
90,412 KB
testcase_22 AC 285 ms
133,376 KB
testcase_23 AC 290 ms
133,376 KB
testcase_24 AC 325 ms
133,988 KB
testcase_25 AC 330 ms
134,016 KB
testcase_26 AC 230 ms
89,124 KB
testcase_27 AC 331 ms
111,964 KB
testcase_28 AC 321 ms
133,660 KB
testcase_29 AC 317 ms
133,508 KB
testcase_30 AC 314 ms
133,504 KB
testcase_31 AC 314 ms
133,208 KB
testcase_32 AC 178 ms
88,556 KB
testcase_33 AC 175 ms
88,448 KB
testcase_34 AC 232 ms
97,408 KB
testcase_35 AC 233 ms
97,408 KB
権限があれば一括ダウンロードができます

ソースコード

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