#770313 (PyPy3) No.1975 Zigzag Sequence

• 問題: No.1975 Zigzag Sequence
• ユーザー: shobonvip
• 提出日時: 2022-06-11 19:05:59
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 309 ms / 2,000 ms
• コード長: 2,002 bytes
• コンパイル時間: 262 ms
• コンパイル使用メモリ: 82,500 KB
• 実行使用メモリ: 127,024 KB
• 最終ジャッジ日時: 2024-09-22 05:57:54
• 合計ジャッジ時間: 8,976 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# a[i] a[j] a[k]
# which a[i] > a[j] < a[k]
# について, 2^(i+k-2)
# 2^iを入れる a[i]に
class BIT:
    """
    <Attention> 0-indexed.
    query ... return the sum [0 to m]
    sum ... return the sum [a to b]
    sumall ... return the sum [all]
    add ... 'add' number to element (be careful that it doesn't set a value.)
    search ... the sum version of bisect.right
    output ... return the n-th element
    listout ... return the BIT list
    """
    
    def query(self, m):
        res = 0
        while m > 0:
            res += self.bit[m]
            m -= m&(-m)
        return res
    
    def sum(self, a, b):
        return self.query(b)-self.query(a)
    
    def sumall(self):
        bitlen = self.bitlen-1
        return self.query(bitlen)
    
    def add(self, m, x):
        m += 1
        bitlen = len(self.bit)
        while m <= bitlen-1:
            self.bit[m] += x
            m += m&(-m)
        return
    
    def search(self, a):
        tmpsum = 0
        i = 0
        k = (self.bitlen-1).bit_length()
        while k >= 0:
            tmpk = 2**k
            if i+tmpk <= self.bitlen-1:
                if tmpsum+self.bit[i+tmpk] < a:
                    tmpsum += self.bit[i+tmpk]
                    i += tmpk
            k = k-1
        return i+1
    
    def output(self, a):
        return self.query(a+1)-self.query(a)
    
    def listout(self):
        return self.bit
    
    def __init__(self, a):
        self.bitlen = a
        self.bit = [0]*a
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}
n = int(input())
a = list(map(int,input().split()))
a_c = compress(a)
m = len(a_c)
bit = BIT(m+2)
#i時点で, a[i] についての 2^i の和
bitA = BIT(m+2)
#bitA ... a[i] > a[j] となる a[j] についての, 2^i の和
bitB = BIT(m+2)
#bitB ... a[i] < a[j] となる a[j] についての, 2^i の和
mod = 10**9 + 7
nibeki = [0] * (n+1)
nibeki[0] = 1
for i in range(n):
    nibeki[i+1] = nibeki[i] * 2 % mod
ans = 0
for i in range(n):
    targ = a_c[a[i]]
    ans += bitA.sum(0, targ) * nibeki[n-i-1] % mod
    ans %= mod
    ans += bitB.sum(targ+1, m+1) * nibeki[n-i-1] % mod
    ans %= mod
    bit.add(targ, nibeki[i])
    bitA.add(targ, bit.sum(targ+1, m+1))
    bitB.add(targ, bit.sum(0, targ))
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX