結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー brthyyjpbrthyyjp
提出日時 2021-12-29 09:18:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 870 ms / 5,000 ms
コード長 3,715 bytes
コンパイル時間 512 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 95,516 KB
最終ジャッジ日時 2024-10-03 13:36:17
合計ジャッジ時間 8,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
52,864 KB
testcase_01 AC 33 ms
52,736 KB
testcase_02 AC 33 ms
52,960 KB
testcase_03 AC 32 ms
53,376 KB
testcase_04 AC 32 ms
53,336 KB
testcase_05 AC 100 ms
77,160 KB
testcase_06 AC 227 ms
80,132 KB
testcase_07 AC 99 ms
76,684 KB
testcase_08 AC 198 ms
80,844 KB
testcase_09 AC 548 ms
87,888 KB
testcase_10 AC 372 ms
78,820 KB
testcase_11 AC 398 ms
84,160 KB
testcase_12 AC 633 ms
91,452 KB
testcase_13 AC 241 ms
80,132 KB
testcase_14 AC 255 ms
92,672 KB
testcase_15 AC 538 ms
92,288 KB
testcase_16 AC 714 ms
93,840 KB
testcase_17 AC 870 ms
94,532 KB
testcase_18 AC 422 ms
92,288 KB
testcase_19 AC 765 ms
95,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegTree:
    def __init__(self, init_val, seg_ide, lazy_ide, f, g, h):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()

        self.seg_ide = seg_ide
        self.lazy_ide = lazy_ide

        self.f = f
        self.g = g
        self.h = h

        self.seg = [seg_ide]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.f(self.seg[2*i], self.seg[2*i+1])

        self.size = [0]*2*self.num
        for i in range(self.n):
            self.size[i+self.num] = 1
        for i in range(self.num-1, 0, -1):
            self.size[i] = self.size[2*i] + self.size[2*i+1]

        self.lazy = [lazy_ide]*2*self.num

    def update(self, i, x):
        i += self.num
        self.seg[i] = x
        while i:
            i = i >> 1
            self.seg[i] = self.f(self.seg[2*i], self.seg[2*i+1])

    def calc(self, i):
        return self.g(self.seg[i], self.lazy[i], self.size[i])

    def calc_above(self, i):
        i = i >> 1
        while i:
            self.seg[i] = self.f(self.calc(2*i), self.calc(2*i+1))
            i = i >> 1

    def propagate(self, i):
        self.seg[i] = self.g(self.seg[i], self.lazy[i], self.size[i])
        self.lazy[2*i] = self.h(self.lazy[2*i], self.lazy[i])
        self.lazy[2*i+1] = self.h(self.lazy[2*i+1], self.lazy[i])
        self.lazy[i] = self.lazy_ide

    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)

    def query(self, l, r):
        l += self.num
        r += self.num
        lm = l // (l & -l)
        rm = r // (r & -r) -1
        self.propagate_above(lm)
        self.propagate_above(rm)

        al = self.seg_ide
        ar = self.seg_ide
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l = l >> 1
            r = r >> 1
        return self.f(al, ar)

    def oprerate_range(self, l, r, a):
        l += self.num
        r += self.num
        lm = l // (l & -l)
        rm = r // (r & -r) -1
        self.propagate_above(lm)
        self.propagate_above(rm)
        while l < r:
            if l & 1:
                self.lazy[l] = self.h(self.lazy[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.lazy[r] = self.h(self.lazy[r], a)
            l = l >> 1
            r = r >> 1

        self.calc_above(lm)
        self.calc_above(rm)

    def __str__(self): # for debug
        arr = [self.query(i,i+1) for i in range(self.n)]
        return str(arr)

f = lambda x, y: x+y
g = lambda x, a, s: a*s if a is not None else x

h = lambda a, b: b if b is not None else a

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():
    n = int(input())
    q = int(input())
    sa = 0
    sb = 0
    segA = LazySegTree([0]*n, 0, None, f, g, h)
    segB = LazySegTree([0]*n, 0, None, f, g, h)
    for i in range(q):
        x, l, r = map(int, input().split())
        if x == 0:
            ca = segA.query(l, r+1)
            cb = segB.query(l, r+1)
            if ca > cb:
                sa += ca
            elif ca < cb:
                sb += cb
        elif x == 1:
            segA.oprerate_range(l, r+1, 1)
            segB.oprerate_range(l, r+1, 0)
        else:
            segA.oprerate_range(l, r+1, 0)
            segB.oprerate_range(l, r+1, 1)

    sa += segA.query(0, segA.n)
    sb += segB.query(0, segB.n)
    print(sa, sb)

if __name__ == '__main__':
    main()
0