結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー gew1fw
提出日時 2025-06-12 13:06:08
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,803 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,992 KB
実行使用メモリ 852,344 KB
最終ジャッジ日時 2025-06-12 13:10:59
合計ジャッジ時間 5,297 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    ops = []
    for _ in range(K):
        L = int(data[ptr])
        ptr += 1
        R = int(data[ptr])
        ptr += 1
        C = int(data[ptr])
        ptr += 1
        H = int(data[ptr])
        ptr += 1
        ops.append((L, R, C, H))

    # Collect events for each operation
    events = []
    for idx in range(K):
        L, R, C, H = ops[idx]
        events.append((L, 'add', idx))
        events.append((R + 1, 'remove', idx))

    # Sort events. For the same position, 'add' comes before 'remove'
    events.sort(key=lambda x: (x[0], 0 if x[1] == 'add' else 1))

    # For each block i, store the list of operations in time order
    block_ops = [[] for _ in range(N + 2)]  # 1-based to N

    current_ops = []
    event_ptr = 0
    for i in range(1, N + 1):
        # Process events at position i
        while event_ptr < len(events) and events[event_ptr][0] == i:
            typ = events[event_ptr][1]
            idx = events[event_ptr][2]
            if typ == 'add':
                # Insert into current_ops in order (by time)
                bisect.insort(current_ops, idx)
            else:
                # Remove from current_ops
                pos = bisect.bisect_left(current_ops, idx)
                if pos < len(current_ops) and current_ops[pos] == idx:
                    current_ops.pop(pos)
            event_ptr += 1
        # For block i, the current_ops are the operations affecting it, sorted by time
        # Make a copy to store for block i
        block_ops[i] = current_ops.copy()

    # Precompute prefix sums and colors for each block
    prefix_sums = []
    colors = []
    for i in range(1, N + 1):
        sum_h = 0
        ps = [0]
        clrs = []
        for idx in block_ops[i]:
            _, _, C, H = ops[idx]
            sum_h += H
            ps.append(sum_h)
            clrs.append(C)
        prefix_sums.append(ps)
        colors.append(clrs)

    # Process queries
    for _ in range(Q):
        I = int(data[ptr])
        ptr += 1
        X = int(data[ptr])
        ptr += 1
        target = X - 0.5
        ps = prefix_sums[I - 1]
        clrs = colors[I - 1]
        if not clrs:
            print(-1)
            continue
        # Find the largest m where ps[m] <= target
        m = bisect.bisect_right(ps, target) - 1
        if m >= len(clrs):
            print(-1)
        else:
            if m < 0:
                print(-1)
            else:
                if ps[m + 1] > target:
                    print(clrs[m])
                else:
                    print(-1)

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