結果

問題 No.2281 K → K-1 01 Flip
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:56:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,704 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 52,736 KB
最終ジャッジ日時 2025-03-31 17:57:53
合計ジャッジ時間 8,577 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    Q = int(data[idx])
    idx +=1
    S = data[idx]
    idx +=1

    # Preprocess the original runs: list of (pos, char)
    runs = []
    if N ==0:
        pass
    else:
        current_char = S[0]
        current_len =1
        for c in S[1:]:
            if c == current_char:
                current_len +=1
            else:
                runs.append( (current_len, current_char) )
                current_char = c
                current_len =1
        runs.append( (current_len, current_char) )
    # Precompute the prefix sums and run starts
    prefix = [0]*(len(runs)+1)
    for i in range(len(runs)):
        prefix[i+1] = prefix[i] + runs[i][0]
    run_starts = [0]*(len(runs)+1)
    for i in range(len(runs)):
        run_starts[i+1] = run_starts[i] + runs[i][0]

    for _ in range(Q):
        L = int(data[idx])-1  # 0-based
        idx +=1
        R = int(data[idx])-1  # 0-based [inclusive]
        idx +=1
        K = int(data[idx])
        idx +=1
        
        # Find the runs that intersect with the substring [L, R] (0-based)
        # Find the first run that has start >= L, using binary search
        # run_starts is the prefix sum of run lengths. Find the largest i where run_starts[i] <= L
        left = 0
        right = len(run_starts)-1
        start_run = 0
        while left <= right:
            mid = (left+right)//2
            if run_starts[mid] <= L:
                start_run = mid
                left = mid +1
            else:
                right = mid-1
        # the first run is start_run
        current_run_start = start_run
        total_length = R - L +1
        current_runs = []
        accumulated = run_starts[start_run]
        while current_run_start < len(runs):
            run_len, run_char = runs[current_run_start]
            run_end = accumulated + run_len -1
            seg_start = max(L, accumulated)
            seg_end = min(R, run_end)
            if seg_start > seg_end:
                break
            current_runs.append( (seg_end - seg_start +1, run_char) )
            accumulated += run_len
            current_run_start +=1
        
        # Now process current_runs
        # Simulate the operations
        stack = []
        for l, c in current_runs:
            if stack and stack[-1][1] == c:
                stack[-1] = (stack[-1][0] + l, c)
            else:
                stack.append( (l, c) )
            # After merging, check if can apply operations
            while True:
                # Check the last element of stack
                if len(stack) <1:
                    break
                cl, cc = stack[-1]
                if cl < K:
                    break
                # We can apply at least one operation
                ops = cl // K
                total_ops = ops
                new_l = cl % K
                replace_l = ops * (K-1)
                replace_c = '1' if cc == '0' else '0'
                stack.pop()
                if new_l >0:
                    if stack and stack[-1][1] == cc:
                        stack[-1] = (stack[-1][0] + new_l, cc)
                    else:
                        stack.append( (new_l, cc) )
                if replace_l >0:
                    if stack and stack[-1][1] == replace_c:
                        stack[-1] = (stack[-1][0] + replace_l, replace_c)
                    else:
                        stack.append( (replace_l, replace_c) )
                # Check if after replacement, we can apply more operations
                while True:
                    changed = False
                    # Check the new element
                    if len(stack)>=1:
                        nl, nc = stack[-1]
                        if nc == replace_c:
                            if nl >= K:
                                ops = nl // K
                                total_ops += ops
                                new_l = nl % K
                                stack.pop()
                                replace_l = ops * (K-1)
                                replace_c = '1' if nc == '0' else '0'
                                if new_l >0:
                                    if stack and stack[-1][1] == nc:
                                        stack[-1] = (stack[-1][0] + new_l, nc)
                                    else:
                                        stack.append( (new_l, nc) )
                                if replace_l >0:
                                    if stack and stack[-1][1] == replace_c:
                                        stack[-1] = (stack[-1][0] + replace_l, replace_c)
                                    else:
                                        stack.append( (replace_l, replace_c) )
                                changed = True
                                nc = replace_c
                        while len(stack)>=2:
                            a_l, a_c = stack[-2]
                            b_l, b_c = stack[-1]
                            if a_c == b_c:
                                stack.pop()
                                stack[-1] = (a_l + b_l, a_c)
                                if stack[-1][0] >= K:
                                    changed = True
                                    break
                            else:
                                break
                    if not changed:
                        break
        # The total length is the sum of the stack
        min_length = sum( l for l, c in stack )
        print( min_length )
        
if __name__ == "__main__":
    main()
0