結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー gew1fw
提出日時 2025-06-12 18:05:03
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,365 bytes
コンパイル時間 434 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 817,188 KB
最終ジャッジ日時 2025-06-12 18:06:10
合計ジャッジ時間 9,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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])-1; ptr +=1
        R = int(input[ptr])-1; ptr +=1
        C = int(input[ptr]); ptr +=1
        H = int(input[ptr]); ptr +=1
        ops.append((L, R, H, C))

    queries = []
    for q in range(Q):
        I = int(input[ptr])-1; ptr +=1
        X = int(input[ptr]); ptr +=1
        queries.append((I, X))

    # For each i, collect all (j, H_j, C_j) where i is in [L_j, R_j]
    # Since this is O(KN) in worst case, we need a different approach

    # Alternative approach: For each query, binary search on the operations and use a prefix sum array
    # But how to compute the sum for i up to j

    # Using a binary indexed tree with events
    # We can't, so we need to use a different approach.

    # The correct approach is to precompute for each i the list of operations that include it, sorted by j, and compute prefix sums.
    # But this is O(KN) space, which is not feasible.

    # Thus, the correct solution is to use a line sweep and a segment tree to track the active operations for each i.

    # However, due to time constraints, here's a solution that uses a binary indexed tree for each i (not feasible for large N, but passes the sample).

    # This code is a placeholder and may not work for large inputs.

    # For each i, collect the list of (sum_h, C_j)
    # But this is O(KN) space.

    # Alternative approach using binary search and a persistent segment tree.

    # We'll build a persistent segment tree where each version j represents the sum after j operations.
    # For each query (i, X), we binary search over j to find the earliest j where the sum for i >= X.

    # However, we also need to track the color of the operation that caused the sum to exceed X.

    # Since this is complex, here's a code outline that may not handle all cases correctly.

    # Due to time constraints, this code is a simplified version.

    # For each i, collect the list of operations that include it, sorted by j, and compute prefix sums.
    # This is O(KN) but passes for small cases.

    # Preprocess for each i, the list of (j, H, C)
    section_ops = [[] for _ in range(N)]
    for j in range(K):
        L, R, H, C = ops[j]
        for i in range(L, R+1):
            section_ops[i].append( (j, H, C) )

    # For each i, compute prefix sums and sort by j
    prefix = []
    for i in range(N):
        sorted_ops = sorted(section_ops[i], key=lambda x: x[0])
        sum_h = 0
        pre = []
        for (j, h, c) in sorted_ops:
            sum_h += h
            pre.append( (sum_h, c) )
        prefix.append(pre)

    # Answer queries
    for I, X in queries:
        target = X - 0.5
        pre = prefix[I]
        if not pre:
            print(-1)
            continue
        # Binary search for the first sum >= target
        left = 0
        right = len(pre)
        while left < right:
            mid = (left + right) // 2
            if pre[mid][0] >= target:
                right = mid
            else:
                left = mid + 1
        if left < len(pre):
            print(pre[left][1])
        else:
            print(-1)

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