結果

問題 No.1222 -101
ユーザー 👑 SPD_9X2
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
R+- and 0調
imos
00
0
0index
dp[0index] =
11
00index
→3^?
-1 or 1()→(2)
-1 or 1()→(1)
0()  -1,0,1 0dp
0() → 00
dp1 &
dp
X,dp
realdp[i] * inv(X)
XinvX
"""
#0-indexed , [a,b)
#calc
class SegTree:
def __init__(self,N,first):
self.NO = 2**(N-1).bit_length()
self.First = first
self.data = [first] * (2*self.NO)
def calc(self,l,r):
return l+r
def update(self,ind,x):
ind += self.NO - 1
self.data[ind] = x
while ind >= 0:
ind = (ind - 1)//2
self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])
def query(self,l,r):
L = l + self.NO
R = r + self.NO
s = self.First
while L < R:
if R & 1:
R -= 1
s = self.calc(s , self.data[R-1])
if L & 1:
s = self.calc(s , self.data[L-1])
L += 1
L >>= 1
R >>= 1
return s
def inverse(a,mod): #amod
return pow(a,mod-2,mod)
from sys import stdin
import sys
N,M = map(int,stdin.readline().split())
T = SegTree(N+1,0)
T.update(0,1)
mod = 10**9+7
X = 1
R = [ (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] += 1
of = 0
LEFT = 0
half = inverse(2,mod)
for i in range(1,N+1):
of += OS[i]
l,p = R[i]
#print (i,of)
if p == 1:
of -= 1
continue
elif of == 0:
tmpsum = T.query(LEFT,i) * half
T.update(i,tmpsum % mod)
X *= 2
X %= mod
else:
X *= 2
X %= mod
#
if p == 0:
LEFT = max(LEFT,l)
#print (LEFT,X)
print (T.query(LEFT,N+1) * X % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0