結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
|
提出日時 | 2022-06-10 22:08:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 401 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,660 KB |
実行使用メモリ | 110,208 KB |
最終ジャッジ日時 | 2024-09-21 06:22:22 |
合計ジャッジ時間 | 10,668 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
class BIT(): def __init__(self,n,mod=0): self.BIT = [0]*(n+1) self.num = n self.mod = mod """ return A[1] + A[2] + ... A[idx] in O(log n) """ def query(self,idx): res_sum = 0 mod = self.mod while idx > 0: res_sum += self.BIT[idx] if mod: res_sum %= mod idx -= idx&(-idx) return res_sum """ A[idx] += in O(log n) """ def update(self,idx,x): mod = self.mod while idx <= self.num: self.BIT[idx] += x if mod: self.BIT[idx] %= mod idx += idx&(-idx) return import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 10**9 + 7 N = int(input()) A = li() val = sorted(set(A)) comp = {e:i+1 for i,e in enumerate(val)} A = [comp[a] for a in A] n = len(comp) res_big = [1] * N res_small = [1] * N fw = BIT(n) for i,a in enumerate(A): res_big[i] *= fw.query(a-1) res_big[i] %= mod res_small[i] *= (pow(2,i,mod)-1-fw.query(a)) % mod res_small[i] %= mod fw.update(a,pow(2,i,mod)) #print(res_big,res_small) fw = BIT(n) for i in range(N)[::-1]: a = A[i] res_big[i] *= fw.query(a-1) res_big[i] %= mod res_small[i] *= (pow(2,N-1-i,mod)-1-fw.query(a)) % mod res_small[i] %= mod fw.update(a,pow(2,N-1-i,mod)) ans = sum(res_big) + sum(res_small) print(ans % mod) #print(res_big) #print(res_small)