結果
問題 |
No.1975 Zigzag Sequence
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:38:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 290 ms / 2,000 ms |
コード長 | 3,152 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 81,932 KB |
実行使用メモリ | 132,892 KB |
最終ジャッジ日時 | 2025-03-20 20:38:42 |
合計ジャッジ時間 | 7,499 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) A = list(map(int, data[1:N+1])) if N < 3: print(0) return # Coordinate compression sorted_A = sorted(set(A)) rank = {v:i for i, v in enumerate(sorted_A)} max_rank = len(sorted_A) - 1 # Precompute pow2 pow2 = [1] * (N + 1) for i in range(1, N + 1): pow2[i] = (pow2[i-1] * 2) % MOD class FenwickTree: def __init__(self, size): self.size = size self.tree = [0] * (self.size + 2) def update(self, idx, val): idx += 1 # 1-based index for Fenwick Tree while idx <= self.size + 1: self.tree[idx] = (self.tree[idx] + val) % MOD idx += idx & -idx def query(self, idx): # sum [0..idx] (inclusive of original rank, but Fenwick Tree uses 1-based) res = 0 idx += 1 # 1-based index while idx > 0: res = (res + self.tree[idx]) % MOD idx -= idx & -idx return res # Preprocess left sum_x and sum_x_large left_ft = FenwickTree(max_rank) sum_left_small = [0] * N sum_left_large = [0] * N for i in range(N): r = rank[A[i]] # Sum of elements < A[i] sum_small = left_ft.query(r - 1) # Sum of elements > A[i] = total_sum - sum <= A[i] total_sum = left_ft.query(max_rank) sum_large = (total_sum - left_ft.query(r)) % MOD sum_left_small[i] = sum_small sum_left_large[i] = sum_large # Update Fenwick tree with current element's contribution (2^{i-1}) val = pow2[i] # 2^(i) since 0-based here. 2^{i} = 2^{(i+1) -1} ? Wait, for x, the exponent is x-1 # Since in code, i is 0-based. For x, which is 1-based, i runs from 0 to N-1 in the loop (x from 1 to N) # So x = i+1. 2^{x-1} = 2^{i} left_ft.update(r, pow2[i]) # Preprocess right sum_z and sum_z_large right_ft = FenwickTree(max_rank) sum_right_small = [0] * N sum_right_large = [0] * N for i in reversed(range(N)): r = rank[A[i]] # Sum of elements < A[i] sum_small = right_ft.query(r - 1) # Sum of elements > A[i] = total_sum - sum <= A[i] total_sum = right_ft.query(max_rank) sum_large = (total_sum - right_ft.query(r)) % MOD sum_right_small[i] = sum_small sum_right_large[i] = sum_large # Update Fenwick tree with current element's contribution (2^{n - (i+1)}) # because i is 0-based. original z is i+1 (1-based) exp = N - (i + 1) val = pow2[exp] right_ft.update(r, val) total = 0 for i in range(N): s1 = sum_left_small[i] s2 = sum_right_small[i] contrib_peak = (s1 * s2) % MOD s3 = sum_left_large[i] s4 = sum_right_large[i] contrib_valley = (s3 * s4) % MOD total = (total + contrib_peak + contrib_valley) % MOD print(total % MOD) if __name__ == '__main__': main()