結果

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

    # Read all operations
    layers = [[] for _ in range(N+1)]  # 1-based indexing for blocks

    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
        # Record the operation for each block in [L, R]
        for i in range(L, R+1):
            layers[i].append((H, C))

    # Precompute prefix sums for each block's layers
    prefix_sums = []
    colors = []
    for i in range(N+1):
        sum_h = 0
        sums = []
        cs = []
        for h, c in layers[i]:
            sum_h += h
            sums.append(sum_h)
            cs.append(c)
        prefix_sums.append(sums)
        colors.append(cs)

    # Process queries
    output = []
    for _ in range(Q):
        I = int(data[ptr])
        ptr += 1
        X = int(data[ptr])
        ptr += 1
        x = X - 0.5

        sums = prefix_sums[I]
        cs = colors[I]

        if not sums:
            output.append("-1")
            continue

        total = sums[-1]
        if total < x:
            output.append("-1")
            continue

        # Find the largest index where sum <= x
        idx = bisect.bisect_right(sums, x)
        if idx == 0:
            # x is in the first layer
            output.append(str(cs[0]))
        else:
            # Check if x is in the idx-th layer (0-based)
            if idx > len(sums):
                output.append("-1")
            else:
                output.append(str(cs[idx]))

    print('\n'.join(output))

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