結果

問題 No.1975 Zigzag Sequence
ユーザー prussian_coderprussian_coder
提出日時 2022-06-10 22:57:04
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 359 ms / 2,000 ms
コード長 1,199 bytes
コンパイル時間 1,125 ms
コンパイル使用メモリ 81,332 KB
実行使用メモリ 133,572 KB
最終ジャッジ日時 2023-10-21 05:37:04
合計ジャッジ時間 8,716 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,300 KB
testcase_01 AC 42 ms
53,300 KB
testcase_02 AC 42 ms
53,300 KB
testcase_03 AC 101 ms
76,796 KB
testcase_04 AC 84 ms
76,312 KB
testcase_05 AC 258 ms
92,380 KB
testcase_06 AC 230 ms
98,196 KB
testcase_07 AC 98 ms
76,872 KB
testcase_08 AC 172 ms
84,112 KB
testcase_09 AC 311 ms
117,704 KB
testcase_10 AC 215 ms
92,220 KB
testcase_11 AC 233 ms
95,056 KB
testcase_12 AC 103 ms
77,224 KB
testcase_13 AC 41 ms
53,324 KB
testcase_14 AC 41 ms
53,324 KB
testcase_15 AC 39 ms
53,324 KB
testcase_16 AC 39 ms
53,324 KB
testcase_17 AC 40 ms
53,324 KB
testcase_18 AC 167 ms
87,800 KB
testcase_19 AC 174 ms
87,800 KB
testcase_20 AC 214 ms
90,000 KB
testcase_21 AC 214 ms
90,000 KB
testcase_22 AC 292 ms
132,516 KB
testcase_23 AC 299 ms
132,516 KB
testcase_24 AC 340 ms
133,308 KB
testcase_25 AC 346 ms
133,572 KB
testcase_26 AC 240 ms
88,656 KB
testcase_27 AC 359 ms
111,396 KB
testcase_28 AC 326 ms
133,044 KB
testcase_29 AC 328 ms
132,780 KB
testcase_30 AC 325 ms
132,780 KB
testcase_31 AC 324 ms
132,780 KB
testcase_32 AC 186 ms
87,800 KB
testcase_33 AC 185 ms
88,064 KB
testcase_34 AC 243 ms
96,908 KB
testcase_35 AC 247 ms
96,908 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