結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー lam6er
提出日時 2025-04-15 23:10:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,703 bytes
コンパイル時間 523 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 901,828 KB
最終ジャッジ日時 2025-04-15 23:13:01
合計ジャッジ時間 6,983 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 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

    # For each block, store the list of (Hk, Ck) of operations affecting it, in order.
    blocks = [[] for _ in range(N+1)]  # blocks[1..N]

    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
        # For each block in L..R, append (H, C)
        # However, doing this directly is O(K*N), which is impossible for large K and N.
        # Thus, this approach is not feasible for the given constraints.
        # This code is only for demonstration and will not pass large test cases.
        for i in range(L, R+1):
            blocks[i].append((H, C))

    # Precompute prefix sums and color lists for each block
    prefix_sums = []
    color_lists = []
    for i in range(1, N+1):
        sum_h = 0
        sums = [0]
        colors = []
        for h, c in blocks[i]:
            sum_h += h
            sums.append(sum_h)
            colors.append(c)
        prefix_sums.append(sums)
        color_lists.append(colors)

    # Process queries
    for _ in range(Q):
        I = int(data[ptr])
        ptr += 1
        X = int(data[ptr])
        ptr += 1
        h = X - 0.5
        sums = prefix_sums[I-1]
        colors = color_lists[I-1]
        idx = bisect.bisect_right(sums, h) - 1
        if idx < 0 or idx >= len(colors):
            print(-1)
        else:
            print(colors[idx])

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