結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ああいいああいい
提出日時 2022-01-07 10:48:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,024 ms / 5,000 ms
コード長 1,643 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 90,880 KB
最終ジャッジ日時 2024-04-26 07:38:26
合計ジャッジ時間 13,552 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,096 KB
testcase_01 AC 39 ms
52,352 KB
testcase_02 AC 40 ms
52,736 KB
testcase_03 AC 40 ms
52,608 KB
testcase_04 AC 40 ms
52,096 KB
testcase_05 AC 128 ms
75,904 KB
testcase_06 AC 219 ms
77,440 KB
testcase_07 AC 185 ms
77,332 KB
testcase_08 AC 202 ms
77,888 KB
testcase_09 AC 949 ms
83,584 KB
testcase_10 AC 656 ms
79,360 KB
testcase_11 AC 598 ms
80,988 KB
testcase_12 AC 959 ms
84,888 KB
testcase_13 AC 251 ms
77,696 KB
testcase_14 AC 558 ms
86,016 KB
testcase_15 AC 1,473 ms
90,368 KB
testcase_16 AC 1,632 ms
90,496 KB
testcase_17 AC 2,024 ms
90,880 KB
testcase_18 AC 1,136 ms
90,008 KB
testcase_19 AC 1,267 ms
88,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


class SegTree:
    def __init__(self,n):
        k = 1
        while k < n:
            k <<= 1
        self.n = k
        self.dat = [0] * (2 * self.n - 1)
        self.lazy = [0] * (2 * self.n - 1)
    def eval(self,k,l,r):
        if self.lazy[k] == -1:return
        if k < self.n-1:
            self.lazy[k*2+1] = self.lazy[k]
            self.lazy[k*2+2] = self.lazy[k]
        self.dat[k] = self.lazy[k] * (r-l)
        self.lazy[k] = -1
    def update(self,a,b,x,k=0,l=0,r=-1):
        if r == -1:r = self.n
        self.eval(k,l,r)
        if r <= a or b <= l:return
        if a <= l and r <= b:
            self.lazy[k] = x
            self.eval(k,l,r)
            return
        self.update(a,b,x,k*2+1,l,(l+r)//2)
        self.update(a,b,x,k*2+2,(l+r)//2,r)
        self.dat[k] = self.dat[k*2+1]+self.dat[k*2+2]
    def getsum(self,a,b,k=0,l=0,r=-1):
        if r == -1:r = self.n
        self.eval(k,l,r)
        if r <= a or b <= l:return 0
        if a <= l and r <= b:
            return self.dat[k]
        return self.getsum(a,b,k*2+1,l,(l+r)//2)+self.getsum(a,b,k*2+2,(l+r)//2,r)

N = int(input())
Q = int(input())
sega = SegTree(N)
segb = SegTree(N)
pointa = 0
pointb = 0
for _ in range(Q):
    x,l,r = map(int,input().split())
    r += 1
    if x == 0:
        a = sega.getsum(l,r)
        b = segb.getsum(l,r)
        if a < b:
            pointb += b
        elif b < a:
            pointa += a
    elif x == 1:
        sega.update(l,r,1)
        segb.update(l,r,0)
    else:
        sega.update(l,r,0)
        segb.update(l,r,1)
a = sega.getsum(0,N)
b  =segb.getsum(0,N)
pointa += a
pointb += b
print(pointa,pointb)
0