結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 21:59:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 542 ms / 2,000 ms |
コード長 | 2,119 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 124,672 KB |
最終ジャッジ日時 | 2024-09-21 06:17:34 |
合計ジャッジ時間 | 12,300 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
mod = 1000000007 def main(): import sys input = sys.stdin.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) 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, w): if w <= 0: return 0 x = 0 k = 1 << (self.size.bit_length() - 1) while k: if x + k <= self.size and self.tree[x + k] < w: w -= self.tree[x + k] x += k k >>= 1 return x + 1 N = int(input()) A = list(map(int, input().split())) A_unique = sorted(list(set(A))) I = {a: [] for a in A_unique} for i, a in enumerate(A): I[a].append(i + 1) ans = 0 # asc bit_left = Bit(N) bit_right = Bit(N) pow2 = [1] for i in range(1, N+1): bit_left.add(i, pow2[-1]) bit_right.add(N - i + 1, pow2[-1]) pow2.append((pow2[-1] * 2) % mod) for a in A_unique: for i in I[a]: bit_left.add(i, -pow2[i - 1]) bit_right.add(i, -pow2[N - i]) for i in I[a]: val_l = bit_left.sum(i) val_r = bit_right.sum(N) - bit_right.sum(i) ans = (ans + (val_l * val_r)%mod)%mod # desc bit_left = Bit(N) bit_right = Bit(N) pow2 = [1] for i in range(1, N + 1): bit_left.add(i, pow2[-1]) bit_right.add(N - i + 1, pow2[-1]) pow2.append((pow2[-1] * 2) % mod) for a in A_unique[::-1]: for i in I[a]: bit_left.add(i, -pow2[i - 1]) bit_right.add(i, -pow2[N - i]) for i in I[a]: val_l = bit_left.sum(i) val_r = bit_right.sum(N) - bit_right.sum(i) ans = (ans + (val_l * val_r) % mod) % mod print(ans) if __name__ == '__main__': main()