結果

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

ソースコード

diff # 

import sys
import bisect

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

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

    queries = []
    for _ in range(Q):
        I = int(input[ptr]); ptr +=1
        X = int(input[ptr]); ptr +=1
        queries.append( (I-1, X-0.5) )  # I is 1-based, convert to 0-based

    # For each block, collect all ops that cover it, in order
    # Using event-based approach
    events = []
    for k in range(K):
        L, R, C, H = ops[k]
        events.append( (L-1, 'start', k) )  # 0-based
        events.append( (R, 'end', k) )      # R is exclusive

    events.sort(key=lambda x: (x[0], x[1] == 'start'))

    from collections import defaultdict
    block_ops = defaultdict(list)
    active_ops = []

    current_i = 0
    event_ptr = 0
    for i in range(N):
        while event_ptr < len(events) and events[event_ptr][0] == i:
            typ = events[event_ptr][1]
            k = events[event_ptr][2]
            if typ == 'start':
                bisect.insort(active_ops, k)
            else:
                pos = bisect.bisect_left(active_ops, k)
                if pos < len(active_ops) and active_ops[pos] == k:
                    active_ops.pop(pos)
            event_ptr += 1
        # Now, active_ops contains all k where op k covers i+1 (since i is 0-based)
        # For block i+1 (1-based), but in our code, i is 0-based (0..N-1)
        block_ops[i] = list(active_ops)

    # Precompute prefix sums and colors for each block
    prefix_sums = dict()
    colors = dict()
    for i in range(N):
        ops_list = block_ops[i]
        sum_h = 0
        ps = [0]
        cs = []
        for k in ops_list:
            L, R, C, H = ops[k]
            sum_h += H
            ps.append(sum_h)
            cs.append(C)
        prefix_sums[i] = ps
        colors[i] = cs

    # Process queries
    for I, X in queries:
        if I >= N:
            print(-1)
            continue
        ps = prefix_sums.get(I, [0])
        cs = colors.get(I, [])
        total = ps[-1]
        if total <= X:
            print(-1)
            continue
        # Find the largest t where ps[t] <= X
        t = bisect.bisect_right(ps, X) - 1
        if t < 0 or t >= len(cs):
            print(-1)
        else:
            print(cs[t])

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