結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー gew1fw
提出日時 2025-06-12 18:05:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,927 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 200,536 KB
最終ジャッジ日時 2025-06-12 18:06:36
合計ジャッジ時間 6,942 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 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

    L = []
    R = []
    C = []
    H = []
    for _ in range(K):
        Lk = int(input[ptr]); ptr +=1
        Rk = int(input[ptr]); ptr +=1
        Ck = int(input[ptr]); ptr +=1
        Hk = int(input[ptr]); ptr +=1
        L.append(Lk)
        R.append(Rk)
        C.append(Ck)
        H.append(Hk)

    # Persistent BIT (each version is a list of the BIT state after each operation)
    # However, implementing a persistent BIT with range updates is complex.
    # For the sake of this problem, we'll use a different approach.

    # Precompute for each i, the list of operations that include i, sorted by k.
    # This is O(K log N) time using a segment tree.

    class SegmentTreeNode:
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.ops = []

        def is_leaf(self):
            return self.l == self.r

    def build(l, r):
        node = SegmentTreeNode(l, r)
        if l != r:
            mid = (l + r) // 2
            node.left = build(l, mid)
            node.right = build(mid+1, r)
        return node

    def insert(node, l, r, k):
        if node.r < l or node.l > r:
            return
        if l <= node.l and node.r <= r:
            node.ops.append(k)
            return
        insert(node.left, l, r, k)
        insert(node.right, l, r, k)

    root = build(1, N)
    for k in range(K):
        insert(root, L[k], R[k], k)

    # For each query, collect all ops that include I, sorted by k
    # Then compute prefix sums and binary search

    def get_ops(node, i):
        ops = []
        if node.is_leaf():
            return node.ops.copy()
        if node.left.l <= i <= node.left.r:
            ops += get_ops(node.left, i)
        else:
            ops += get_ops(node.right, i)
        ops += node.ops
        return ops

    for _ in range(Q):
        I = int(input[ptr]); ptr +=1
        X = int(input[ptr]); ptr +=1
        X_target = X - 0.5

        # Collect all ops that include I
        ops_k = get_ops(root, I)
        # Sort the ops by k (ascending)
        ops_k.sort()
        # Compute prefix sums
        prefix = []
        sum_h = 0
        for k in ops_k:
            sum_h += H[k]
            prefix.append(sum_h)
        # Binary search for X_target
        idx = bisect.bisect_left(prefix, X_target)
        if idx < len(prefix):
            # Check if the found operation includes I
            k = ops_k[idx]
            if L[k] <= I <= R[k]:
                print(C[k])
            else:
                # This should not happen since the ops are those that include I
                print(-1)
        else:
            print(-1)

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