結果
問題 | No.1222 -101 |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-04 23:05:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 374 ms / 2,000 ms |
コード長 | 2,916 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 100,780 KB |
最終ジャッジ日時 | 2024-11-26 20:56:47 |
合計ジャッジ時間 | 7,315 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
"""Rが違うのを利用する→右端で+- and 0を調整できる多分imos法0でない区間に突入していたら0を置かない0の区間の帳尻合わせは?最後に0を置いたindexで管理?dp[最後に0を置いたindex] = 満たす通り数で管理できる?1の区間の右端はどうせ1通りに決まる0の区間の右端は、最後に0を置いたindexにより分岐なんの区間にも属さない→3^?を最後に掛ければいい-1 or 1の区間(中間)→どちらか好きな方を置く(2)-1 or 1の区間(最期)→決まったほうを置く(1)0の区間(中間) → -1,0,1好きなのを置ける 0を置いた場合、dpを更新0の区間(最期) → 0を一度でも置いていた場合は自由、そうでない場合は0dpを1箇所更新する & 全体に掛けるなので、dp配列に入れた時点でかけていた数字が分ればなんとかなる?全体にかけている数字Xを用意していおいて,実際のdp配列にはrealdp[i] * inv(X)を入れておけばいい取り出すときはXをかけ、戻すときはinvXを書ける→普通のセグ木で解ける"""#0-indexed , 半開区間[a,b)#calc変更で演算変更class SegTree:def __init__(self,N,first):self.NO = 2**(N-1).bit_length()self.First = firstself.data = [first] * (2*self.NO)def calc(self,l,r):return l+rdef update(self,ind,x):ind += self.NO - 1self.data[ind] = xwhile ind >= 0:ind = (ind - 1)//2self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])def query(self,l,r):L = l + self.NOR = r + self.NOs = self.Firstwhile L < R:if R & 1:R -= 1s = self.calc(s , self.data[R-1])if L & 1:s = self.calc(s , self.data[L-1])L += 1L >>= 1R >>= 1return sdef inverse(a,mod): #aのmodを法にした逆元を返すreturn pow(a,mod-2,mod)from sys import stdinimport sysN,M = map(int,stdin.readline().split())T = SegTree(N+1,0)T.update(0,1)mod = 10**9+7X = 1R = [ (None,None) for i in range(N+1) ]OS = [0] * (N+1) #1or-1の区間開始を告げるfor loop in range(M):l,r,p = map(int,stdin.readline().split())R[r] = (l,abs(p))if p != 0:OS[l] += 1of = 0LEFT = 0half = inverse(2,mod)for i in range(1,N+1):of += OS[i]l,p = R[i]#print (i,of)if p == 1:of -= 1continueelif of == 0:tmpsum = T.query(LEFT,i) * halfT.update(i,tmpsum % mod)X *= 2X %= modelse:X *= 2X %= mod#切り捨てフェーズif p == 0:LEFT = max(LEFT,l)#print (LEFT,X)print (T.query(LEFT,N+1) * X % mod)