結果

問題 No.2901 Logical Sum of Substring
ユーザー lam6er
提出日時 2025-03-26 15:57:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,952 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 129,060 KB
最終ジャッジ日時 2025-03-26 15:58:54
合計ジャッジ時間 8,742 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    Q = int(input[ptr])
    ptr +=1
    queries = []
    for _ in range(Q):
        query = input[ptr]
        if query == '1':
            i = int(input[ptr+1])
            v = int(input[ptr+2])
            queries.append( (1, i-1, v) )
            ptr +=3
        else:
            l = int(input[ptr+1])
            r = int(input[ptr+2])
            queries.append( (2, l-1, r-1) )
            ptr +=3

    target = (1 << K) -1

    # Precompute bits for each number
    bits_for_num = []
    for num in A:
        bits = []
        for b in range(K):
            if (num >> b) & 1:
                bits.append(b)
        bits_for_num.append(bits)

    # Segment tree to check if any element in [l, r] is target
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.tree = [False] * (4 * self.n)
            self.build(0, 0, self.n-1, data)

        def build(self, node, l, r, data):
            if l == r:
                self.tree[node] = (data[l] == target)
                return
            mid = (l + r) // 2
            self.build(2*node+1, l, mid, data)
            self.build(2*node+2, mid+1, r, data)
            self.tree[node] = self.tree[2*node+1] or self.tree[2*node+2]

        def update(self, node, l, r, idx, value):
            if l == r:
                self.tree[node] = (value == target)
                return
            mid = (l + r) // 2
            if idx <= mid:
                self.update(2*node+1, l, mid, idx, value)
            else:
                self.update(2*node+2, mid+1, r, idx, value)
            self.tree[node] = self.tree[2*node+1] or self.tree[2*node+2]

        def query(self, node, l, r, ql, qr):
            if r < ql or l > qr:
                return False
            if ql <= l and r <= qr:
                return self.tree[node]
            mid = (l + r) // 2
            left = self.query(2*node+1, l, mid, ql, qr)
            right = self.query(2*node+2, mid+1, r, ql, qr)
            return left or right

    st = SegmentTree(A)

    for query in queries:
        if query[0] == 1:
            i, v = query[1], query[2]
            A[i] = v
            # Update bits_for_num
            new_bits = []
            for b in range(K):
                if (v >> b) & 1:
                    new_bits.append(b)
            bits_for_num[i] = new_bits
            st.update(0, 0, N-1, i, v)
        else:
            l, r = query[1], query[2]
            # Check if any element is target
            has_target = st.query(0, 0, N-1, l, r)
            if has_target:
                print(1)
                continue
            # Sliding window approach to find minimal window with all K bits
            last_occurrence = [0] * K
            count = 0
            left = l
            min_length = float('inf')
            for right in range(l, r + 1):
                # Update count and last_occurrence for bits in A[right]
                for b in bits_for_num[right]:
                    if last_occurrence[b] == 0:
                        count += 1
                    last_occurrence[b] += 1
                # Try to shrink the window from the left
                while count == K:
                    current_length = right - left + 1
                    if current_length < min_length:
                        min_length = current_length
                    # Move left pointer
                    for b in bits_for_num[left]:
                        last_occurrence[b] -= 1
                        if last_occurrence[b] == 0:
                            count -= 1
                    left += 1
            if min_length != float('inf'):
                print(min_length)
            else:
                print(-1)

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