結果

問題 No.1222 -101
ユーザー chineristACchineristAC
提出日時 2020-10-08 22:00:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,710 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 86,880 KB
実行使用メモリ 77,684 KB
最終ジャッジ日時 2023-09-27 12:01:39
合計ジャッジ時間 6,007 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,576 KB
testcase_01 AC 72 ms
71,336 KB
testcase_02 AC 117 ms
77,684 KB
testcase_03 AC 75 ms
71,608 KB
testcase_04 AC 77 ms
71,344 KB
testcase_05 AC 74 ms
71,344 KB
testcase_06 AC 73 ms
71,460 KB
testcase_07 AC 72 ms
71,364 KB
testcase_08 AC 74 ms
71,384 KB
testcase_09 AC 73 ms
71,188 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegmentTree():
    __slots__ = ["merge","merge_unit","operate","merge_operate","operate_unit","n","data","lazy"]
    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[(v<<1)]=self.operate(self.data[(v<<1)],ope)
        self.data[(v<<1)+1]=self.operate(self.data[(v<<1)+1],ope)
        self.lazy[v<<1]=self.merge_operate(self.lazy[(v<<1)],ope)
        self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    def remerge_above(self,i):
        while i:
            c = self.merge(self.data[i],self.data[i^1])
            i>>=1
            self.data[i]=self.operate(c,self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res>>32

import sys

input = sys.stdin.buffer.readline

mod = 10**9+7
mask = 2**32 - 1

def merge(x,y):
    s = ((x>>32) + (y>>32)) % mod
    num = (x&mask) + (y&mask)
    return (s<<32) + num

merge_unit = 0

def operate(x,ope):
    s,num = x>>32,x&mask
    b,c = ope>>32,ope&mask
    s = (b*s + c*num) % mod
    return (s<<32)+num

def merge_operate(x,y):
    b1,c1 = x>>32,x&mask
    b2,c2 = y>>32,y&mask
    return (((b1*b2)%mod)<<32)+((b2*c1+c2)%mod)

operate_unit = 1<<32

N,M = map(int,input().split())
cond = [None for i in range(N+1)]
for _ in range(M):
    l,r,p = map(int,input().split())
    cond[r] = (l,p)

init = [1 for i in range(N+1)]
init[0] = (1<<32) + 1
dp = LazySegmentTree(N+1,init,merge,merge_unit,operate,merge_operate,operate_unit)
for i in range(1,N+1):
    if cond[i]:
        l,p = cond[i]
        if p==0:
            tmp = dp.query(0,i)
            dp.update(i,i+1,tmp)
            dp.update(l,i,1<<33)
            dp.update(0,l,0)
        else:
            dp.update(l,i,0)
    else:
        tmp = dp.query(0,i)
        dp.update(i,i+1,tmp)
        dp.update(0,i,1<<33)
    check = [dp.query(j,j+1) for j in range(N+1)]

print(dp.query(0,N+1))
0