結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー lam6er
提出日時 2025-04-15 22:14:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,084 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 445,432 KB
最終ジャッジ日時 2025-04-15 22:16:54
合計ジャッジ時間 6,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

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

    queries = []
    for _ in range(Q):
        I = int(data[ptr])
        X = int(data[ptr+1])
        queries.append((I, X))
        ptr += 2

    # Line sweep to collect operations for each section
    events = []
    for k in range(K):
        L, R, C, H = operations[k]
        events.append((L, 'start', k))
        events.append((R + 1, 'end', k))
    events.sort()

    current_ops = set()
    section_ops = [[] for _ in range(N + 1)]  # 1-based indexing

    event_ptr = 0
    for i in range(1, N + 1):
        while event_ptr < len(events) and events[event_ptr][0] <= i:
            pos, typ, k = events[event_ptr]
            if typ == 'start':
                current_ops.add(k)
            else:
                if k in current_ops:
                    current_ops.remove(k)
            event_ptr += 1
        # Convert current_ops to a sorted list by k
        sorted_ops = sorted(current_ops)
        section_ops[i] = sorted_ops

    # Precompute prefix sums and colors for each section
    prefix_sums = [[] for _ in range(N + 1)]
    colors = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        sum_h = 0
        for k in section_ops[i]:
            sum_h += operations[k][3]
            prefix_sums[i].append(sum_h)
            colors[i].append(operations[k][2])

    # Process queries
    for I, X in queries:
        T = X - 0.5
        ops = section_ops[I]
        if not ops:
            print(-1)
            continue
        sum_list = prefix_sums[I]
        idx = bisect.bisect_left(sum_list, T)
        if idx < len(sum_list):
            print(colors[I][idx])
        else:
            print(-1)

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