結果

問題 No.2901 Logical Sum of Substring
ユーザー 👑 hahhohahho
提出日時 2024-04-25 14:32:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,269 ms / 3,000 ms
コード長 4,463 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 276,720 KB
最終ジャッジ日時 2024-09-20 20:51:09
合計ジャッジ時間 31,640 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
67,840 KB
testcase_01 AC 68 ms
68,096 KB
testcase_02 AC 166 ms
79,488 KB
testcase_03 AC 164 ms
79,488 KB
testcase_04 AC 155 ms
79,360 KB
testcase_05 AC 156 ms
79,360 KB
testcase_06 AC 161 ms
79,488 KB
testcase_07 AC 174 ms
79,728 KB
testcase_08 AC 1,153 ms
273,984 KB
testcase_09 AC 1,121 ms
273,288 KB
testcase_10 AC 1,136 ms
273,984 KB
testcase_11 AC 1,179 ms
273,696 KB
testcase_12 AC 1,191 ms
274,332 KB
testcase_13 AC 1,230 ms
272,968 KB
testcase_14 AC 1,217 ms
276,708 KB
testcase_15 AC 1,180 ms
276,164 KB
testcase_16 AC 1,181 ms
276,720 KB
testcase_17 AC 960 ms
251,968 KB
testcase_18 AC 1,063 ms
252,668 KB
testcase_19 AC 991 ms
252,176 KB
testcase_20 AC 1,164 ms
273,672 KB
testcase_21 AC 1,154 ms
273,732 KB
testcase_22 AC 1,269 ms
274,372 KB
testcase_23 AC 1,108 ms
252,416 KB
testcase_24 AC 930 ms
251,840 KB
testcase_25 AC 941 ms
252,224 KB
testcase_26 AC 960 ms
260,936 KB
testcase_27 AC 964 ms
261,408 KB
testcase_28 AC 967 ms
261,604 KB
testcase_29 AC 1,096 ms
270,228 KB
testcase_30 AC 1,107 ms
269,692 KB
testcase_31 AC 1,077 ms
269,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import *

T = TypeVar('T')
BinaryOperator = Callable[[T, T], T]
E = TypeVar('E')

class SegmentTree(Generic[E]):
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。(ただし単位元は添加可能)
    """

    @classmethod
    def all_identity(cls, operator: BinaryOperator[E], identity: E, size: int) -> 'SegmentTree[E]':
        return cls(operator, identity, [identity] * (2 << (size - 1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator: BinaryOperator[E], identity: E, data: MutableSequence[E]) -> 'SegmentTree[E]':
        size = 1 << (len(data) - 1).bit_length()
        temp = [identity] * (2 * size)
        temp[size:size + len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2 * i], data[2 * i + 1])
        return cls(operator, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator: BinaryOperator[E], identity: E, data: MutableSequence[E]):
        self.op = operator
        self.id = identity
        self.data = data
        self.size = len(data) // 2

    def reduce(self, l: int, r: int) -> E:
        l += self.size
        r += self.size
        vl = self.id
        vr = self.id

        while l < r:
            if l & 1:
                vl = self.op(vl, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.op(self.data[r], vr)
            l >>= 1
            r >>= 1
        return self.op(vl, vr)

    def __getitem__(self, i: Union[slice, int]) -> E:
        if isinstance(i, slice):
            return self.reduce(
                0 if i.start is None else i.start,
                self.size if i.stop is None else i.stop)
        return self.data[i + self.size]

    def __setitem__(self, i: int, v: E):
        i += self.size
        while i:
            self.data[i] = v
            v = self.op(self.data[i ^ 1], v) if i & 1 else self.op(v, self.data[i ^ 1])
            i >>= 1

    def __iter__(self) -> Iterator[E]:
        return iter(self.data[self.size:])

def min2(x, y):
    return x if x < y else y

INF = 2**60


def solve(k, aa, queries):

    MASK = (1<<k)-1
    def op(x, y):
        x_prefix, x_suffix, x_opt, x_block = x
        y_prefix, y_suffix, y_opt, y_block = y
        z_opt = min2(x_opt, y_opt)
        i = 0
        for p, t in reversed(y_prefix):
            while i < len(x_suffix) and x_suffix[i][0]|p != MASK:
                i += 1
            if i >= len(x_suffix):
                break
            z_opt = min2(z_opt, t + x_suffix[i][1])
        z_prefix = x_prefix[:]
        if z_prefix[-1][0] != MASK:
            for v, t in y_prefix:
                u = v|z_prefix[-1][0]
                if u != z_prefix[-1][0]:
                    z_prefix.append((u, t+x_block))
        z_suffix = y_suffix[:]
        if z_suffix[-1][0] != MASK:
            for v, l in x_suffix:
                u = v|z_suffix[-1][0]
                if u != z_suffix[-1][0]:
                    z_suffix.append((u, l+y_block))
        return z_prefix, z_suffix, z_opt, x_block+y_block

    seg = SegmentTree.from_initial_data(op,
                                        identity=([(0, 0)], [(0, 0)], INF, 0),
                                        data=[([(0, 0), (s, 1)] if s != 0 else [(0, 0)],
                                               [(0, 0), (s, 1)] if s != 0 else [(0, 0)],
                                               1 if s == MASK else INF,
                                               1) for i,s in enumerate(aa)]
                                        )

    res = []
    for query in queries:
        mode, *tokens = query
        if mode == 1:
            i, v = tokens
            seg[i] = ([(0, 0), (v, 1)] if v != 0 else [(0, 0)],
                      [(0, 0), (v, 1)] if v != 0 else [(0, 0)],
                      1 if v == MASK else INF,
                      1)
        else:
            l, r = tokens
            p = seg[l:r][2]
            res.append(p if p < INF else -1)
    return res


n, k = map(int,input().split())
aa = list(map(int,input().split()))
q = int(input())
queries = []
for _ in range(q):
    a,b,c = map(int,input().split())
    queries.append((a,b-1,c))
print(*solve(k, aa, queries), sep='\n')
0