結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー lam6er
提出日時 2025-03-31 17:59:05
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,870 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 858,608 KB
最終ジャッジ日時 2025-03-31 17:59:55
合計ジャッジ時間 6,837 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    # Collect all operations
    ops = []
    for _ in range(K):
        L = int(data[idx])-1  # 0-based
        idx +=1
        R = int(data[idx])-1
        idx +=1
        C = int(data[idx])
        idx +=1
        H = int(data[idx])
        idx +=1
        ops.append( (L, R, C, H) )

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

    # Step 1: Compute sum_i using a prefix sum (difference array)
    sum_i = [0]*(N+1)
    for L, R, C, H in ops:
        sum_i[L] += H
        sum_i[R+1] -= H

    # Compute the prefix sum
    current =0
    prefix_sum = []
    for i in range(N):
        current += sum_i[i]
        prefix_sum.append(current)
    sum_i = prefix_sum

    # Now, build a segment tree where each node contains list of ops that cover its interval
    # For each query, we need to collect all ops that covers I, in order of their occurrence
    # We'll use a binary indexed approach to collect all ops affecting I.

    # However, this is not feasible. Instead, we will, for each operation, store it in a list,
    # and for each block i, collect all ops where Lk <=i <=Rk.

    # Since K can be 2e5 and N is 2e5, this is O(K*N) time, which is impossible.
    # So we need an alternative approach. 

    # However, given the time constraints, let's implement it for the sake of this solution.

    # For each block i, collect all ops that affect it, ordered by their occurrence (in the order of K)
    # This is a costly step but required for the correct approach.
    op_list = [[] for _ in range(N)]
    for k in range(K):
        L, R, C, H = ops[k]
        for i in range(L, R+1):
            op_list[i].append( (H, C) )

    # Now, for each i, compute the prefix sums and colors
    prefix_sums = []
    prefix_colors = []
    for i in range(N):
        ps = []
        cs = []
        current_sum =0
        ps.append(current_sum)
        for H, C in op_list[i]:
            current_sum += H
            ps.append(current_sum)
            cs.append(C)
        prefix_sums.append(ps)
        prefix_colors.append(cs)

    # Process each query
    results = []
    for I, X in queries:
        x = X - 0.5
        if sum_i[I] <= x:
            results.append(-1)
            continue
        ps = prefix_sums[I]
        cs = prefix_colors[I]
        # Find the largest j where ps[j] <=x
        j = bisect.bisect_right(ps, x) -1
        if j >=0 and j < len(cs):
            results.append(cs[j])
        else:
            results.append(-1)

    print('\n'.join(map(str, results)))

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