結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,352 KB
testcase_01 AC 44 ms
52,736 KB
testcase_02 AC 44 ms
52,352 KB
testcase_03 AC 44 ms
52,224 KB
testcase_04 AC 44 ms
52,224 KB
testcase_05 AC 137 ms
76,160 KB
testcase_06 AC 240 ms
77,440 KB
testcase_07 AC 195 ms
77,464 KB
testcase_08 AC 210 ms
77,448 KB
testcase_09 AC 1,090 ms
83,584 KB
testcase_10 AC 744 ms
79,488 KB
testcase_11 AC 672 ms
80,868 KB
testcase_12 AC 1,091 ms
85,016 KB
testcase_13 AC 272 ms
78,336 KB
testcase_14 AC 660 ms
86,400 KB
testcase_15 AC 1,773 ms
90,496 KB
testcase_16 AC 1,913 ms
90,240 KB
testcase_17 AC 2,267 ms
90,880 KB
testcase_18 AC 1,252 ms
90,192 KB
testcase_19 AC 1,377 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